首页 > 代码库 > NOIP模拟·20141105题解

NOIP模拟·20141105题解

2024-07-31 08:24:51   218人阅读

【A、韩信点兵】

   

    结论题+模板题，用到了中国剩余定理，维基百科上讲的就比较详细，这里就不再赘述了……

    对于这题，我们先利用中国剩余定理($x \equiv \sum{a_i \times m_i (m_i^{-1} \mod p_i)}\, \mod (\prod{p_i})$)找到当前人数的最小可行解$x_0$，（如果$x_0$已经超过了$N$，直接输出无解即可）这时不难证明，对于任何一个可行解，都有 $$x_i = x_0 + k \times \prod{P_i},k \in \mathbb{N}$$

    我们的目标是找到不超过$N$的最大可行解x‘,那么答案就是$N - x‘$。注意这里如果直接枚举$k$的话有一个测试点会超时（看起来我的数据规模还是挺良心的……只卡掉了10分）。正确的做法是先用$N$减去$x_0$，这时剩下的部分就是$N - x‘ +

k \times \prod{P_i},k \in \mathbb{N}$，那么我们只需用这个结果对$\prod{P_i}$取余即可得到答案。

  

 1 #include <cstdio>
 2 #include <cctype>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <queue>
 6 #include <cmath>
 7 #include <iostream>
 8 
 9 
10 typedef long long LL;
11 using namespace std;
12 inline int lowbit(int x){return x & -x;}
13 int gcd(int a, int b){return (!a) ? b : gcd(b % a, b);}
14 template<typename T>T exgcd(T a, T b, T &x, T &y){
15     if(!a){x = 0, y = 1; return b;}
16     T d = exgcd(b % a, a, y, x);
17     x -= (b/a) * y;
18     return d;
19 }
20 /*=====================================*/
21 inline LL inv(LL a, LL mod){
22     LL x, y;
23     if(exgcd(a, mod, x, y) != 1)return -1;
24     return (x % mod + mod) % mod;
25 }
26 LL n, M = 1, N[11], e, S = 0;
27 int P[11], a[11], m;
28 
29 inline void init(){
30     cin >> n >> m;
31     for(int i = 0;i < m;++i){
32         cin >> P[i] >> a[i];
33         M *= P[i];
34     }
35     for(int i = 0;i < m;++i){
36         N[i] = M / P[i];
37         e = N[i] * inv(N[i], P[i]) % M;
38         S = (S + e * a[i]) % M;
39     }
40 }
41 
42 inline void work(){
43     LL x, y;
44     exgcd<LL>(1, M, x, y);
45     x = ((x * S % M) + M ) % M;
46     if(x > n){cout << -1 << endl;return;}
47     cout << (n - x) % M << endl;
48 }
49 
50 int main(){
51     #if defined DEBUG
52     freopen("test", "r", stdin);
53     #else
54     freopen("HanXin.in", "r", stdin);
55     freopen("HanXin.out", "w", stdout);
56     #endif*/
57     
58     init();
59     
60     work();
61     
62     return 0;
63 }
中国剩余定理

 

【B、月考统计】

    经典模型——差分约束系统。设第i位同学的分数为$x_i$，所有同学的最低分数为0. 则统计表中的每条息$i,j,a_{ij}$都可以形式化为 $$x_i - x_j \le a_{ij}$$。

    对于这样一组不等式，我们可以抽象化出图论模型：每个同学都抽象为一个节点，再设一个起点0，表示所有同学的最低分数。对于每个不等式$x_i - x_j \le a_{ij}$，我们都从点i到点j连一条权值为$-a_{ij}$的有向边，表示从起点到点j的最长路权和最多比起点到i的最长路权和大$-a_{ij}$（可以用最长路的三角形不等式证明）。对于这样的图，用spfa求出从起点到每个点的最长路权和就是答案。

 

 1 /*=============================================================================================================================*/
 2 /*======================================================Code by Asm.Def========================================================*/
 3 /*=============================================================================================================================*/
 4 #include <cstdio>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <cmath>
 8 #include <cctype>
 9 #include <memory.h>
10 #include <vector>
11 #include <set>
12 #include <string>
13 #include <cstring>
14 #include <map>
15 #include <queue>
16 #include <deque>
17 #include <stack>
18 #include <ctime>
19 #include <iterator>
20 #include <functional>
21 #include <cstdlib>
22 using namespace std;
23 /*===================================================================================*/
24 #define forall(it,v) for(__typeof(v.begin()) it = v.begin();it < v.end();++it) 
25 #define pb push_back
26 #define REP(i,j,k) for(i = j;i <= k;++i)
27 #define REPD(i,j,k) for(i = j;i >= k;--i)
28 #define iter(v) v::iterator
29 typedef long long LL;
30 template<typename T> void getint(T &x){
31     char c = getchar();
32     while(!isdigit(c))c = getchar();
33     x = c - ‘0‘;
34     while(isdigit(c = getchar()))x = x * 10 + c - ‘0‘;
35 }
36 /*============================================================================================*/
37 const int maxn = 2000 + 5;
38 int N, M;
39 struct edge{
40     int to, w;
41     edge(int T, int W):to(T), w(W){}
42 };
43 vector<edge> adj[maxn];
44 
45 queue<int> Q;
46 bool inQ[maxn] = {0};
47 int dis[maxn] = {0}, cnt[maxn] = {0};
48 inline void init(){
49     cin >> N >> M;
50     int i, x, y, a;
51     while(M--){
52         cin >> x >> y >> a;
53         adj[x].push_back(edge(y, -a));
54     }
55     for(i = 1;i <= N;++i)
56         Q.push(i);inQ[i] = 1;cnt[i] = 1;
57 }
58 inline void work(){
59     int i, t;
60     iter(vector<edge>) it;
61     while(!Q.empty()){
62         t = Q.front();Q.pop();inQ[t] = 0;
63         for(it = adj[t].begin();it != adj[t].end();++it)
64             if(dis[t] + it->w > dis[it->to]){
65                 dis[it->to] = dis[t] + it->w;
66                 if(!inQ[it->to]){
67                     if(cnt[it->to] == N){
68                         cout << "SOMEONE LAY!" << endl;
69                         return;
70                     }
71                     Q.push(it->to);inQ[it->to] = 1;++cnt[it->to];
72                 }
73             }
74     }
75     for(i = 1;i <= N;++i)
76         cout << dis[i] << ‘ ‘;
77 }
78 
79 int main(){
80     #ifdef DEBUG
81     freopen("test", "r", stdin);
82     #else
83     freopen("ExamStat.in", "r", stdin);
84     freopen("ExamStat.out", "w", stdout);
85     #endif
86     
87     init();
88     work();
89     
90     #ifdef DEBUG
91     //cout << endl << (double)clock() / CLOCKS_PER_SEC <<endl;
92     #endif
93     return 0;
94 }
spfa解差分约束

 【C、神奇的压缩机】

    神奇的压缩机，神奇的阅读题……

    这题改编自第21场Andrew Stankevich‘s Contest（俄国的ACM多校训练赛）的Lempel-Ziv Compression……

    当时我的解法是预处理出字符串中每个子串的“满足i小于子串长度且i前缀与i后缀相等的i”的最大值（或 原串的每个后缀的KMP-next数组）……听起来相当拗口，不过套用KMP的预处理过程可以降低思维难度。

 

 1 //Verdict: Accepted 2 
 2 // Submission Date: 2014-10-02 16:34:32
 3 // Time: 8256MS
 4 // Memory: 34624KB
 5 
 6 /*======================================================Code by Asm.Def========================================================*/
 7 #include <cstdio>
 8 #include <iostream>
 9 #include <algorithm>
10 #include <cmath>
11 #include <cctype>
12 #include <memory.h>
13 #include <cstring>
14 #include <cstdlib>
15 using namespace std;
16 #define maxn ((int)4.1e3)
17 
18 typedef long long LL;
19   
20 char ch[maxn];
21 int len = 0, minbit[maxn], *next[maxn];
22 int l[maxn], r[maxn], str[maxn];
23 
24 
25 inline void getnext(int l){
26     int i, j, L = len - l;
27     next[l] = new int[L+2];
28     int *Next = next[l];
29     Next[0] = 0;
30     for(i = 1;i < L;++i){
31         j = Next[i-1] - 1;
32         while(ch[l+i] != ch[l+j+1] && j >= 0)
33             j = Next[j] - 1;
34         if(ch[l+i] == ch[l+j+1])
35             Next[i] = j + 2;
36         else Next[i] = 0;
37     }
38 }
39 void printpro(int i){
40     if(str[i] == i){
41         if(r[i])printpro(r[i]-1);
42         int j;
43         for(j = r[i];j <= i;++j)putchar(ch[j]);
44         return;
45     }
46     printpro(str[i]);
47     printf("(%d,%d)", r[i], l[i]);
48 }
49 int main(){
50     #ifdef DEBUG
51     assert(freopen("test","r",stdin));
52     #endif
53 
54     char c;
55     while(isalpha(c = getchar()))str[len] = len, ch[len++] = c;
56     int i, j, Min, t;
57     for(i = 0;i < len - 1; ++i)
58         getnext(i);
59     minbit[0] = 9;
60     for(i = 1;i < len; ++i){
61         Min = 0x7fffffff;
62         for(j = 0;j < i;++j)
63             if(minbit[j] + (i-j)*9 < Min){
64                 Min = minbit[j] + (i-j)*9;
65                 str[i] = i;
66                 r[i] = j+1;
67             }
68         for(j = 0;j < i; ++j){
69             t = next[j][i-j];
70             if(!t)continue;
71             if(minbit[i-t] + 25 < Min){
72                 Min = minbit[i-t] + 25;
73                 str[i] = i-t;
74                 r[i] = i+1-t-j;
75                 l[i] = t;
76             }
77         }
78         minbit[i] = Min;
79     }
80     printf("%d\n", minbit[len-1]);
81     printpro(len-1);
82     return 0;
83 }
动态规划

NOIP模拟·20141105题解


联系
我们