mix

 1 //polya burnside定理 http://blog.csdn.net/liangzhaoyang1/article/details/72639208
 2 //原题ASIA qingdao  https://nanti.jisuanke.com/t/18515
 3 #include <iostream>
 4 #include <map>
 5 #include <algorithm>
 6 #include <cstring>
 7 
 8 using namespace std;
 9 
10 map<string, bool> vis;
11 int tot;
12 const int LEN = 16;
13 int oo[3][LEN] = {//翻转 旋转 扭转
14     {0, 7, 2, 9, 4, 11, 6, 1, 8, 3, 10, 5, 12, 13, 15, 14},
15     {13, 12, 4, 2, 5, 3, 15, 14, 9, 11, 8, 10, 6, 7, 0, 1},
16     {1, 0, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 14, 15, 12, 13}
17 };
18 bool cir[LEN+5];
19 char sss[LEN+5];
20 int cnts[LEN+5]={0};
21 
22 int cnt(string &s){
23     int res = 0;
24     memset(cir,0,sizeof(cir));
25     int f;
26     for(int i = 0; i < LEN; i++){
27         if(!cir[i]){
28             cir[i] = true;
29             f = i;
30             while(!cir[f = s[f]-'A']){
31                 cir[f] = true;
32             }
33             res++;
34         }
35     }
36     return res;
37 }
38 
39 void bfs(string s){
40     if(vis[s]) return;
41     tot++;
42     vis[s] = true;
43     cnts[cnt(s)]++;
44     string ss = s;
45     for(int i = 0; i < 3; i++){
46         for(int k = 0; k < LEN; k++){
47             s[k] = ss[oo[i][k]];
48         }
49         bfs(s);
50     }
51 }
52 
53 int main(){
54     tot = 0;
55     for(int i = 0; i < LEN; i++)
56         sss[i] = i+'A';
57     sss[LEN] = '';
58     string s = sss;
59     bfs(s);
60     int n;
61     while(cin >> n){
62         long long ans = 0;
63         long long p = 1;
64         for(int i = 1; i <= LEN; i++){
65             p *= n;
66             ans += cnts[i]*p;
67         }
68         ans /= tot;
69         cout << ans << endl;
70     }
71     return 0;
72 }

Gdufe-OJ1459

 1 //polya hdu3923
 2 // https://www.cnblogs.com/lxjshuju/p/6824210.html
 3 #include <bits/stdc++.h>
 4 
 5 using namespace std;
 6 typedef long long LL;
 7 const LL mod=1000000007;
 8 
 9 LL gcd(LL a, LL b){
10     return b==0?a:gcd(b,a%b);
11 }
12 
13 LL power(LL p, LL n){
14     LL ans = 1;
15     while(n){
16         if(n&1)
17             ans = ans*p%mod;
18         p = p*p%mod;
19         n/=2;
20     }
21     return ans;
22 }
23 
24 LL exgcd(LL a, LL b, LL &x, LL &y){
25     if(!b){
26         x = 1;
27         y = 0;
28         return a;
29     }
30     LL d = exgcd(b,a%b,x,y);
31     LL t = x;
32     x = y;
33     y = t - a/b*y;
34     return d;
35 }
36 
37 int main(){
38     int T;
39     cin >> T;
40     int q = 0;
41     while(T--){
42         LL ans = 0;
43         LL n,m;
44         cin >> n >> m;
45         for(LL i = 1; i <= m; i++){
46             ans += power(n,gcd(m,i));
47             ans%=mod;
48         }
49         if(m&1)
50             ans += (m*power(n,m/2+1))%mod;
51         else
52             ans += ((m/2*power(n,m/2+1))%mod+(m/2*power(n,m/2))%mod);
53         ans %= mod;
54         LL x, y;
55         exgcd(2*m,mod,x,y);
56         //x=power(2*n,mod-2)%mod;//另外一种,费马小定理
57         x = (x+mod)%mod;
58         cout << "Case #" << ++q <<": "<< ans*x%mod << endl;
59     }
60     return 0;
61 }

Hdu3923

 1 //poj3070
 2 //矩阵快速幂
 3 //http://blog.csdn.net/wust_zzwh/article/details/52058209
 4 //https://www.cnblogs.com/Commence/p/3976132.html
 5 #include <iostream>
 6 using namespace std;
 7 
 8 struct mat{
 9     int D[3][3];
10 };
11 mat d;
12 
13 mat xx(mat x, mat y){
14     mat z;
15     for(int k = 0; k < 2; k++)
16         for(int i = 0; i < 2; i++)
17             z.D[i][k] = 0;
18     for(int k = 0; k < 2; k++){
19         for(int i = 0; i < 2; i++){
20                 for(int j = 0; j < 2; j++){
21                     z.D[i][j] += x.D[i][k] * y.D[k][j];
22                     z.D[i][j] %= 10000;
23                 }
24         }
25     }
26     return z;
27 }
28 
29 int power(mat a, int b){
30     mat ans;
31     for(int k = 0; k < 2; k++)
32         for(int i = 0; i < 2; i++)
33             ans.D[i][k] = (i==k);
34     while(b){
35         if(b&1)
36             ans = xx(ans,a);
37         a = xx(a,a);
38         b/=2;
39     }
40     return ans.D[0][1];
41 }
42 
43 int solve(int t){
44     d.D[0][0] = d.D[1][0] = d.D[0][1] = 1;
45     d.D[1][1] = 0;
46     int ans = 0;
47     ans = power(d,t);
48     return ans;
49 }
50 
51 int main(){
52     int k;
53     while(cin >> k && k>=0){
54         cout << solve(k) << endl;
55     }
56      return 0;
57 }

Poj3070

 1 //poj3233  矩阵快速幂
 2 //https://www.cnblogs.com/hadilo/p/5903514.html
 3 #include <stdio.h>
 4 
 5 struct mat{
 6     int dd[70][70];
 7 }D,d;
 8 
 9 int n, k, m;
10 
11 mat xx(mat x, mat y){
12     mat c;
13     for(int k = 0; k < n; k++)
14         for(int i = 0; i < n; i++)
15             c.dd[k][i] = 0;
16     for(int k = 0; k < n; k++){
17         for(int i = 0; i < n; i++){
18             if(x.dd[i][k] <= 0)
19                 continue;
20             for(int j = 0; j < n; j++){
21                 if(y.dd[k][j] <= 0)
22                     continue;
23                 c.dd[i][j] += x.dd[i][k] * y.dd[k][j];
24                 c.dd[i][j] %= m;
25             }
26         }
27     }
28     return c;
29 }
30 
31 void power(mat a, int b){
32     while(b){
33         if(b&1){
34             d = xx(d,a);
35         }
36         a = xx(a,a);
37         b/=2;
38     }
39 }
40 
41 int main(){
42     while(~scanf("%d%d%d",&n,&k,&m)){
43         for(int i = 0; i < n; i++){
44             for(int j = 0; j < n; j++)
45                 scanf("%d",&D.dd[i][j]);
46             D.dd[i][i+n] = D.dd[i+n][i+n] = d.dd[i][i] = d.dd[i+n][i+n] = 1;
47         }
48         n*=2;
49         k++;
50         power(D,k);
51         n/=2;
52         for(int i = 0; i < n; i++)
53             d.dd[i][i+n]= (d.dd[i][i+n]-1+m)%m;
54         for(int i = 0; i < n; i++){
55             for(int k = 0; k < n; k++){
56                 if(k!=0)
57                     printf(" ");
58                 printf("%d", d.dd[i][k+n]);
59             }
60             printf("
");
61         }
62     }
63     return 0;
64 }

Poj3233

 1 //快速幂 hdu2276
 2 //https://www.cnblogs.com/zzqc/p/7152684.html
 3 //注意左乘和右乘矩阵，矩阵的方向，矩阵的初始化
 4 #include <stdio.h>
 5 #include <cstring>
 6 
 7 struct mat{
 8     int d[102][102];
 9 };
10 int len;
11 int t[102];
12 int n;
13 
14 mat xx(mat x, mat y){
15     mat z;
16     for(int k = 0; k < len; k++)
17         for(int i = 0; i < len; i++)
18             z.d[i][k] = 0;
19     for(int k = 0; k < len; k++){
20         for(int i = 0; i < len; i++){
21                 for(int j = 0; j < len; j++){
22                     z.d[i][j] += x.d[i][k] * y.d[k][j];
23                     z.d[i][j] %= 2;
24                 }
25         }
26     }
27     return z;
28 }
29 
30 mat power(mat x, int y){
31     mat ans;
32     for(int k = 0; k < len; k++)
33         for(int i = 0; i < len; i++)
34             ans.d[i][k] = (i==k);
35     while(y){
36         if(y&1){
37             ans = xx(ans,x);
38         }
39         x = xx(x,x);
40         y/=2;
41     }
42     return ans;
43 }
44 
45 void solve(){
46     mat a;
47     for(int k = 0; k < len; k++)
48         for(int i = 0; i < len; i++)
49             a.d[i][k] = 0;
50     a.d[len-1][0] = a.d[0][0] = 1;
51     for(int i = 1; i < len; i++){
52         a.d[i-1][i] = a.d[i][i] = 1;
53     }
54     a = power(a,n);
55     for(int i = 0; i < len; i++){
56         int z = 0;
57         for(int k = 0; k < len; k++){
58             z += t[k] * a.d[k][i];
59             z %= 2;
60         }
61         printf("%d", z);
62     }printf("
");
63 }
64 
65 int main(){
66     while(~scanf("%d",&n)){
67         char s[102];
68         scanf("%s",s);
69         len = strlen(s);
70         for(int i = 0; i < len; i++)
71             t[i] = s[i] - '0';
72         solve();
73     }
74     return 0;
75 }

Hdu2276

 1 //欧拉回路 Hdu3018
 2 //http://www.cnblogs.com/buptLizer/archive/2012/04/15/2450297.html
 3 //
 4 #include <iostream>
 5 using namespace std;
 6 
 7 int deg[100010];
 8 int n,m;
 9 int f[100010],odd[100010],cir[100010];
10 bool used[100010];
11 
12 void init(){
13     for(int i = 0; i <= n; i++){
14         deg[i] = 0;
15         used[i] = false;
16         odd[i] = 0;
17         f[i] = i;
18         cir[i] = 0;
19     }
20 }
21 
22 int find(int a){
23     return f[a]==a?a:f[a] = find(f[a]);
24 }
25 
26 void unite(int a, int b){
27     int a1 = find(a), b1 = find(b);
28     if(a1==b1)
29         return;
30     f[a1] = b1;
31 }
32 
33 int main(){
34     while(cin >> n >> m){
35         init();
36         int a,b;
37         for(int i = 0; i < m; i++){
38             cin >> a >> b;
39             deg[a]++;
40             deg[b]++;
41             unite(a,b);
42         }
43         int cnt = 0;
44         for(int i = 1; i <= n; i++){//注意是从1开始
45             int t = find(i);
46             if(!used[t]){
47                 used[t] = true;
48                 cir[cnt++] = t;
49             }
50             if(deg[i]%2==1)
51                 odd[t]++;
52         }
53 
54         int ans = 0;
55         for(int i = 0; i < cnt; i++){
56             if(deg[cir[i]]==0)
57                 continue;
58             if(odd[cir[i]]==0)
59                 ans++;
60             else
61                 ans += odd[cir[i]]/2;
62         }
63         cout << ans << endl;
64     }
65     return 0;
66 }

Hdu3018

 1 //poj2230 欧拉回路
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 struct Edge{
 8     int to, next;
 9 }edge[100005];
10 
11 int head[10005],used[100005],n,m,cnt;
12 
13 void add(int x, int y){
14     edge[cnt].to = y;
15     edge[cnt].next = head[x];
16     head[x] = cnt++;
17 }
18 
19 void dfs(int u){
20     for(int i = head[u]; i!=-1; i=edge[i].next){
21         int v = edge[i].to;
22         if(!used[i]){
23             used[i] = 1;
24             dfs(v);
25         }
26     }
27     printf("%d
", u);
28 }
29 
30 int main(){
31     while(~scanf("%d%d",&n,&m)){
32         cnt = 1;
33         memset(head,-1,sizeof(head));
34         memset(used,0,sizeof(used));
35         int x, y;
36         while(m--){
37             scanf("%d%d",&x,&y);
38             add(x,y);
39             add(y,x);
40         }
41         dfs(1);
42     }
43     return 0;
44 }

Poj2230

 1 //poj1386 欧拉回路
 2 //http://www.cnblogs.com/buptLizer/archive/2012/04/15/2450297.html
 3 #include <iostream>
 4 #include <stdio.h>
 5 #include <cstring>
 6 using namespace std;
 7 
 8 int in[30],out[30];
 9 int f[30];
10 int _rank[30];
11 bool used[30];
12 int n;
13 
14 void init(){
15     for(int i = 0; i < 30; i++){
16         _rank[i] = 1;
17         f[i] = -1;
18         in[i] = 0;
19         out[i] = 0;
20         used[i] = false;
21     }
22 }
23 
24 int find(int a){
25     if(f[a]>=0)
26         return f[a] = find(f[a]);
27     return a;
28 }
29 
30 void unite(int x, int y){
31     int a = find(x), b = find(y);
32     if(a==b)
33         return;
34     if(_rank[a] < _rank[b]){
35         f[a] = b;
36     }else{
37         f[b] = a;
38         if(_rank[a]==_rank[b])
39             _rank[a]++;
40     }
41     return;
42 }
43 
44 int main(){
45     int t;
46     cin >> t;
47     while(t--){
48         init();
49         cin >> n;
50         for(int i = 0; i < n; i++){
51             char a[1010];
52             scanf("%s",a);
53             int len = strlen(a);
54             int x = a[0] - 'a';
55             = used[y] = true;
56             out[x]++;
57             in[y]++;
58             unite(x,y);
59         }
60         int cir = 0;
61         for(int i = 0; i < 30; i++){
62             if(used[i] && f[i]<0){
63                 cir++;
64             }
65         }
66         if(cir > 1){
67             cout << "The door cannot be opened." <<endl;
68             continue;
69         }
70         int j = 0, k = 0, i;
71         for(i = 0; i < 30; i++){
72             if(used[i] && in[i]!=out[i]){
73                 if(in[i]-out[i]==1)
74                     j++;
75                 else if(out[i]-in[i]==1)
76                     k++;
77                 else break;
78             }
79         }
80         if(i<30)
81             cout << "The door cannot be opened." <<endl;
82         else if(!(j+k) || (j==1&&k==1))
83             cout << "Ordering is possible." <<endl;
84         else
85             cout << "The door cannot be opened." <<endl;
86     }
87     return 0;
88 }

Poj1386

 1 //Poj2337 欧拉回路
 2 #include <stdio.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <string>
 6 #include <math.h>
 7 #include <string.h>
 8 
 9 using namespace std;
10 
11 struct E{
12     int to,next,index;
13     bool flag;
14 }edge[2010];
15 
16 int cnt;
17 int head[30], in[30], out[30];
18 string s[1010];
19 int tot, start;
20 int ans[1010];
21 
22 void add(int a, int b, int index){
23     edge[tot].to = b;
24     edge[tot].next = head[a];
25     edge[tot].flag = false;
26     edge[tot].index = index;
27     head[a] = tot++;
28 }
29 
30 void dfs(int t){
31     for(int i = head[t]; i!=-1; i = edge[i].next){
32         if(!edge[i].flag){
33             edge[i].flag = true;
34             dfs(edge[i].to);
35             ans[cnt++] = edge[i].index;
36         }
37     }
38 }
39 
40 int main(){
41     int t;
42     scanf("%d",&t);
43     while(t--){
44         int n;
45         scanf("%d",&n);
46         for(int i = 0; i < n; i++){
47             cin >> s[i];
48         }
49         sort(s,s+n);
50         memset(head,-1,sizeof(head));
51         memset(in,0,sizeof(in));
52         memset(out,0,sizeof(out));
53         tot = 0;
54         start = 0x3f;
55         for(int i = n-1; i >= 0; i--){//因为是邻接表头插法，所以从字典序最大的开始加
56             int len = s[i].length();
57             int l = s[i][0] - 'a';
58             int r = s[i][len-1] - 'a';
59             add(l,r,i);
60             in[r]++;
61             out[l]++;
62             if(l<start)
63                 start = l;
64             if(r<start)
65                 start = r;//起点选择最小的
66         }
67         int q = 0, w = 0;
68         for(int i = 0; i < 30; i++){
69             if(out[i]-in[i] == 1){
70                 q++;
71                 start = i;//如果有出度>入度+1的，为起点
72             }
73             else if(in[i]-out[i] == 1)
74                 w++;
75             else if(in[i]!=out[i])
76                 q=999;
77         }
78         if(!((q==0&&w==0) || (q==1&&w==1))){
79             printf("***
");
80             continue;
81         }
82         cnt = 0;
83         dfs(start);
84         if(cnt!=n){
85             printf("***
");
86             continue;
87         }
88         for(int i = cnt-1; i>=0; i--){
89             cout << s[ans[i]];
90             if(i==0)
91                 printf("
");
92             else
93                 printf(".");
94         }
95     }
96     return 0;
97 }

Poj2337

 1 //Hdu1800 ELFhash
 2 //https://www.cnblogs.com/blvt/p/7953641.html
 3 #include <stdio.h>
 4 #include <algorithm>
 5 #include <string.h>
 6 #include <math.h>
 7 using namespace std;
 8 
 9 int ans;
10 int ha[1010101],num[1010101];
11 int mod = 1010101;
12 
13 int ELFhash(char *s){
14      unsigned int p = 0, q;
15      while(*s){
16          p = (p << 4) + *s++;//h左移4位，当前字符占8位，再加到h中进行杂糅
17          if((q = p & 0x70000000) != 0){ //取h最左四位的值，若均为0，则括号中执行与否没区别，故不执行
18              p ^= q>>24;//用p28-31位的值对p的5~8位进行杂糅
19              p &= ~q;//清空p的最左四位
20          }
21      }
22     return p & 0x7fffffff;
23     //return p;//因为每次都清空了28~31位，最后结果最多也就是28位二进制整数，不会超int
24 }
25 
26 void hash_table(char *s){
27     int k = ELFhash(s);
28     int t = k % mod;
29     /*
30     int cnt1 = 1, cnt2 = 0;
31     while(ha[t] != k && ha[t] != -1){
32         t = (t + cnt1*cnt1 - cnt2*cnt2)%mod;
33         cnt1++,cnt2++;//平方探测法
34     }
35     */
36     while(ha[t] != k && ha[t] != -1){
37         t = (t+1)%mod;
38     }
39     if(ha[t] == -1){
40         ha[t] = k;
41         num[t] = 1;
42     }else{
43         ans = max(ans, ++num[t]);
44     }
45 }
46 
47 int main(){
48     int n;
49     while(~scanf("%d",&n)){
50         memset(ha,-1,sizeof(ha));
51         memset(num,0,sizeof(num));
52         ans = 1;
53         for(int i = 0; i < n; i++){
54             char s[32];
55             scanf("%s",s);
56             int k = 0;
57             while(s[k] == '0')
58                 k++;
59             hash_table(s+k);
60         }
61         printf("%d
", ans);
62     }
63     return 0;
64 }

Hdu1800

 1 //Hdu2444 二分图匹配
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 
 7 #define MAXN 205
 8 using namespace std;
 9 
10 vector<int> g[MAXN];
11 int l[MAXN];
12 bool used[MAXN];
13 int m, n;
14 int ans;
15 
16 bool judge(int v){
17     for(int i = 0; i < g[v].size(); i++){
18         int z= g[v][i];
19         if(l[z] == 0){
20             l[z] = !l[v];//1和-1两种标记，表示属于两个集合
21             used[z] = true;
22             if(!judge(z))
23                 return false;
24         }else if(l[z] == l[v])
25             return false;
26     }
27     return true;
28 }
29 
30 bool tu(){
31     memset(used,false,sizeof(used));
32     memset(l,0,sizeof(l));//注意这里是0
33     for(int i = 1; i <= n; i++){
34         if(g[i].size() && !used[i]){
35             used[i] = true;
36             memset(l,0,sizeof(l));
37             l[i] = 1;//第一个点标记为1
38             if(!judge(i))
39                 return false;
40         }
41     }
42     return true;
43 }
44 
45 bool dfs(int v){
46     for(int i = 0; i < g[v].size(); i++){
47         int z = g[v][i];
48         if(!used[z]){
49             used[z] = true;
50             if(l[z]==-1 || dfs(l[z])){
51                 l[z] = v;
52                 l[v] = z;
53                 return true;
54             }
55         }
56     }
57     return false;
58 }
59 
60 void solve(){
61     memset(l,-1,sizeof(l));
62     for(int i = 1; i <= n; i++){
63         if(l[i]==-1){//l[i]表示i邻接l[i]边
64             memset(used,false,sizeof(used));
65             if(dfs(i))
66                 ans++;
67         }
68     }
69 }
70 
71 int main(){
72     while(cin >> n >> m){
73         for (int i = 0; i < MAXN; i++)
74             g[i].clear();
75         for(int i = 0; i < m; i++){
76             int a, b;
77             cin >> a >> b;
78             g[b].push_back(a);
79             g[a].push_back(b);
80         }
81         if(!tu())//判断是否为二分图
82             printf("No
"); 
83         else{
84             ans = 0;
85             solve();
86             printf("%d
",ans);   
87         }
88     }
89     return 0;
90 }

Hdu2444

 1 //Hdu2255 KM算法
 2 //https://www.cnblogs.com/wenruo/p/5264235.html
 3 #include <stdio.h>
 4 #include <cstring>
 5 #include <algorithm>
 6 #define INF 0x3f3f3f3f
 7 #define N 302
 8 
 9 using namespace std;
10 
11 int n;
12 int g[N][N];
13 int exl[N], exr[N];//好感度
14 bool visl[N], visr[N];//是否被访问
15 int match[N];//match[r]=i,i是r的匹配边
16 int least[N];//r可以被匹配的最低好感度
17 
18 bool dfs(int v){
19     visl[v] = true;
20     for(int i = 0; i < n; i++){
21         if(visr[i])
22             continue;
23         int gg = exl[v]+exr[i]-g[v][i];
24         if(gg == 0){
25             visr[i] = true;
26             if(match[i]==-1 || dfs(match[i])){
27                 match[i] = v;
28                 return true;
29             }
30         }else{
31             least[i] = min(gg, least[i]);
32         }
33     }
34     return false;
35 }
36 
37 int km(){
38     memset(match, -1, sizeof(match));
39     memset(exr, 0, sizeof(exr));
40 
41     for(int i = 0; i < n; i++){//初始好感度是最大的lr
42         exl[i] = g[i][0];
43         for(int j = 1; j < n; j++){
44             exl[i] = max(exl[i], g[i][j]);
45         }
46     }
47 
48     for(int i = 0; i < n; i++){
49         for(int k = 0; k < n; k++)
50             least[k] = INF;//r可以被匹配的最低好感度
51 
52         while(1){//如果找不到就降低期望值，直到找到为止
53             memset(visl,false,sizeof(visl));
54             memset(visr,false,sizeof(visr));
55             if(dfs(i))//匹配  退出
56                 break;
57 
58             // 如果不能找到 就降低期望值
59             int d = INF;
60             for(int j = 0; j < n; j++){
61                 if(!visr[j])
62                     d = min(d, least[j]);// 最小可降低的期望值
63             }
64             for(int j = 0; j < n; j++){
65                 if(visl[j])//所有访问过的女生降低期望值
66                     exl[j] -= d;
67                 if(visr[j])//所有访问过的男生增加期望值(膨胀)
68                     exr[j] += d;
69                 if(!visr[j])//// 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！
70                     least[j] -= d;
71             }
72         }
73     }
74     int ans = 0;
75     for(int h = 0; h < n; h++){
76         ans += g[match[h]][h];
77     }
78     return ans;
79 }
80 
81 int main(){
82     while(~scanf("%d",&n)){
83         for(int i = 0; i < n; i++){
84             for(int k = 0; k < n; k++)
85                 scanf("%d", &g[i][k]);
86         }
87         printf("%d
", km());
88     }
89     return 0;
90 }

Hdu2255

 1 //Poj3020 二分图-最短路径覆盖
 2 //http://blog.csdn.net/lyy289065406/article/details/6647040
 3 //建图是关键，其他常规
 4 //无向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数
 5 #include <iostream>
 6 #include <cstring>
 7 #include <algorithm>
 8 #include <vector>
 9 #define N 402
10 using namespace std;
11 
12 int cnt;
13 int tu[N][N];
14 int used[N];
15 vector<int> g[N];
16 int x1[] = {0,1,-1,0};
17 int y1[] = {1,0,0,-1};
18 int l[N];
19 
20 bool dfs(int v){
21     for(int i = 0; i < g[v].size(); i++){
22         int z = g[v][i];
23         if(!used[z]){
24             used[z] = true;
25             if(l[z]==-1 || dfs(l[z])){
26                 l[z] = v;
27                 return true;
28             }
29         }
30     }
31     return false;
32 }
33 
34 int solve(){
35     int ans = 0;
36     memset(l,-1,sizeof(l));
37     for(int i = 1; i <= cnt; i++){
38         memset(used,false,sizeof(used));
39         if(dfs(i))
40             ans++;
41     }
42     return ans/2;
43 }
44 
45 int main(){
46     int t;
47     cin >> t;
48     while(t--){
49         cnt = 0;
50         int h,w;
51         cin >> h >> w;
52         for(int i = 0; i < N; i++)
53             g[i].clear();
54         for(int i = 0; i < h; i++){
55             for(int k = 0; k < w; k++){
56                 char q;
57                 cin >> q;
58                 if(q=='*')
59                     tu[i][k] = ++cnt;
60                 else
61                     tu[i][k] = -1;
62             }
63         }
64         for(int i = 0; i < h; i++)
65             for(int k = 0; k < w; k++){
66                 if(tu[i][k]!=-1){
67                     for(int j = 0; j < 4; j++){
68                         int xx = i+x1[j], yy = k+y1[j];
69                         if(xx>=0 && yy>=0 && xx<h && yy<w && tu[xx][yy]!=-1){
70                             g[tu[i][k]].push_back(tu[xx][yy]);
71                         }
72                     }
73                 }
74             }
75         cout << cnt-solve() << endl;
76     }
77     return 0;
78 }

Poj3020

  1 //Poj3686 二分图的最佳完美匹配
  2 //http://blog.csdn.net/sixdaycoder/article/details/47720471
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <cstring>
  6 #include <stdio.h>
  7 
  8 #define N 52
  9 #define INF 0x3f3f3f3f
 10 using namespace std;
 11 
 12 int g[N][N];
 13 int c[N][N*N];
 14 int n, m;
 15 int exl[N], exr[N*N];
 16 bool visl[N], visr[N*N];
 17 int match[N*N];
 18 int least[N*N];
 19 
 20 bool dfs(int v){
 21     visl[v] = true;
 22     for(int i = 1; i <= m; i++){
 23         if(visr[i])
 24             continue;
 25         int gg = exl[v]+exr[i]-c[v][i];
 26         if(gg==0){
 27             visr[i] = true;
 28             if(match[i]==-1 || dfs(match[i])){
 29                 match[i] = v;
 30                 return true;
 31             }
 32         }else
 33             least[i] = min(gg,least[i]);
 34     }
 35     return false;
 36 }
 37 
 38 int km(){
 39     for(int i = 1; i <= n; i++){
 40         for(int j = 1; j <= m; j++){
 41             least[j] = INF;
 42         }
 43         while(1){
 44             memset(visl,false,sizeof(visl));
 45             memset(visr,false,sizeof(visr));
 46             if(dfs(i)){
 47                 break;
 48             }
 49 
 50             int d = INF;
 51             for(int j = 1; j <= m; j++){
 52                 if(!visr[j])
 53                     d = min(d, least[j]);
 54             }
 55 
 56             for(int j = 1; j <= n; j++)
 57                 if(visl[j])
 58                     exl[j] -= d;
 59             for(int j = 1; j <= m; j++){
 60                 if(visr[j])
 61                     exr[j] += d;
 62                 else
 63                     least[j] -= d;
 64             }
 65         }
 66     }
 67     int ans = 0;
 68     for(int i = 1; i <= m; i++)
 69         if(match[i]!=-1)
 70             ans += c[match[i]][i];
 71     return ans;
 72 }
 73 
 74 
 75 int main(){
 76     int t;
 77     cin >> t;
 78     while(t--){
 79         memset(g,0,sizeof(g));
 80         memset(c,0,sizeof(c));
 81         memset(match, -1, sizeof(match));
 82         memset(exr, 0, sizeof(exr));
 83         memset(exl, 0, sizeof(exl));
 84 
 85         cin >> n >> m;
 86         for(int i = 1; i <= n; i++)
 87             for(int k = 1 ; k <= m; k++){
 88                 cin>> g[i][k];
 89             }
 90 
 91         for(int i = 1; i <= n; i++){
 92             for(int k = 1 ; k <= n; k++){
 93                 for(int j = 1; j <= m; j++){
 94                     c[i][(k-1)*m+j] = -g[i][j]*k;
 95                 }
 96             }
 97         }
 98         m*=n;
 99         printf("%.6f
",-1.0*km()/n);
100     }
101     return 0;
102 }

Poj3686

 1 //Poj3713 
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <stdio.h>
 6 #include <vector>
 7 
 8 #define N 520
 9 using namespace std;
10 
11 vector<int> g[N];
12 bool has[N], vis[N];
13 int match[N];
14 int n, m;
15 
16 bool dfs(int u, int v){
17     for(int i = 0; i < g[u].size(); i++){
18         int t = g[u][i];
19         if(t==v){
20             if(has[u])
21                 continue;
22             has[u] = true;
23             return true;
24         }
25         if(vis[t])
26             continue;
27         vis[t] = true;
28         if(dfs(match[t],v)){
29             match[t] = u;
30             return true;
31         }
32     }
33     return false;
34 }
35 
36 bool flow(int u,int v){
37     memset(has,0,sizeof(has));
38     for(int i = 0; i < n; i++){
39         match[i] = i;
40     }
41     for(int i = 0; i < 3; i++){
42         memset(vis,false,sizeof(vis));
43         if(!dfs(u,v))
44             return false;
45     }
46     return true;
47 }
48 
49 bool doit(){
50     for(int i = 1; i < n; i++){
51         if(!flow(0,i))
52             return false;
53     }
54     return true;
55 }
56 
57 int main(){
58     while(cin >> n >> m && n && m){
59         for (int i = 0;i < n;++i) {
60             g[i].clear();
61             g[i].push_back(i);
62         }
63         for(int i = 0; i < m; i++){
64             int a, b;
65             cin >> a >> b;
66             g[a].push_back(b);
67             g[b].push_back(a);
68         }
69         if(!doit())
70             cout << "NO" << endl;
71         else
72             cout << "YES" << endl;
73     }
74     return 0;
75 }

Poj3713

 1 /*
 2 Hdu2588 
 3 求k使gcd(k,n)>=m，设a = gcd(k,n) >= m
 4 则 k=a*d,n=a*b(k属于1~n，d与b互质,d<b)
 5 则需要枚举1-n求k，而因为k与n已知，所以a已知，相当于枚举d，因为d b互质,d<b,所以满足(k=a*d && gcd(k,n)>=m)的d的个数等于φ(b)
 6 所以只枚举1-n求φ(b)
 7 
 8 for(a = 1 to n)
 9     if(n/a没有余数)//n=a*b  那么n/a就是b了
10         if(a>=m) //那么n/a就是b了
11         if(n/a>=m)//n=a*b  枚举大于根号n的一半，那么n/(n/a)就是b了
12 */
13 #include <iostream>
14 using namespace std;
15 
16 int n;
17 
18 int euler(int n){
19     int res = n;
20     for(int i = 2; i*i <= n; i++){
21         if(n%i==0){
22             res = res/i*(i-1);
23             while(n%i==0)
24                 n/=i;
25         }
26     }
27     if(n>1)
28         res -= res/n;
29     return res;
30 }
31 
32 int main(){
33     int t;
34     cin >> t;
35     while(t--){
36         int n, m;
37         cin >> n >> m;
38         int ans = 0;
39         for(int i = 1; i*i <= n; i++){
40             if(n%i==0){
41                 if(i>=m)
42                     ans+=euler(n/i);
43                 if(n/i>=m && i*i!=n)
44                     ans+=euler(i);
45             }
46         }
47         cout << ans << endl;
48     }
49     return 0;
50 }

Hdu2588

 1 //Poj3696 强行ac,不知所云
 2 //https://www.cnblogs.com/chenxiwenruo/p/3569146.html
 3 //a*b=c*d  a与c互质时，b整除c，d整除a
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <math.h>
 7 using namespace std;
 8 
 9 typedef long long LL;
10 
11 LL gcd(LL a, LL b){
12     return b?gcd(b,a%b):a;
13 }
14 
15 LL eular(LL n){
16     LL ans = n;
17     for(LL i = 2; i*i <= n; i++){
18         if(n%i==0){
19             ans = ans/i*(i-1);
20             while(n%i==0)
21                 n/=i;
22         }
23     }
24     if(n>1)
25         ans -= ans/n;
26     return ans;
27 }
28 
29 LL mul(LL x, LL y, LL m){
30     LL ans = 0;
31     while(y){
32         if(y&1)
33             ans = (ans+x)%m;
34         x = x*2%m;
35         y>>=1;
36     }
37     return ans;
38 }
39 
40 LL powmod(LL x, LL y, LL m){
41     LL ans = 1;
42     while(y){
43         if(y&1)
44             ans = mul(ans,x,m);
45         x = mul(x,x,m);
46         y>>=1;
47     }
48     return ans;
49 }
50 
51 int main(){
52     int t = 1;
53     LL L;
54     while(cin >> L){
55         if(L == 0) break;
56         LL q = 1LL*9*L/gcd(8,L);
57         LL d = gcd(10,q);
58         if(d != 1){
59             cout << "Case " << t++ << ": 0"<< endl;
60         }else{
61             LL phi = eular(q);
62             LL ans = phi;
63             LL m = sqrt((double)phi);
64             bool flag = false;
65             for(LL i = 1; i <= m; i++){
66                 if(phi%i==0 && powmod(10,i,q)==1){
67                     ans = i;
68                     flag = true;
69                     break;
70                 }
71             }
72             if(!flag){
73                 for(LL i = m; i >= 2; i--){
74                     if(phi%i==0 && powmod(10,phi/i,q)==1){
75                         ans = phi/i;
76                         break;
77                     }
78                 }
79             }
80             cout << "Case "<< t++ << ": " << ans <<endl;
81         }
82     }
83     return 0;
84 }

Poj3696

 1 //Poj2891 中国剩余定理/线性同余方程组（模数不一定互质情况）
 2 //http://blog.csdn.net/acdreamers/article/details/8050018
 3 //http://blog.csdn.net/zmh964685331/article/details/50527894
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <cstring>
 7 #include <stdio.h>
 8 
 9 using namespace std;
10 typedef long long ll;
11 ll n;
12 int m[1000002], a[1000002];
13 
14 ll exgcd(ll a, ll b, ll &x, ll &y){
15     if(b==0){
16         x = 1;
17         y = 0;
18         return a;
19     }
20     ll ans = exgcd(b,a%b,y,x);
21     y -= a/b*x;
22     return ans;
23 }
24 
25 ll gcd(ll a, ll b){
26     return b?gcd(b,a%b):a;
27 }
28 
29 ll china(ll n){
30     ll m1=m[0],a1=a[0],m2,a2,k1,k2,x0,mgcd,c;
31     for(int i = 1; i < n; i++){
32         m2 = m[i], a2 = a[i];
33         c = a2-a1;
34         mgcd=exgcd(m1,m2,k1,k2);
35         if(c%mgcd){
36             return -1;
37         }
38         x0 = c/mgcd*k1;
39         ll t = m2/mgcd;
40         x0 = (x0%t+t)%t;
41         a1+=m1*x0;
42         m1*=m2/mgcd;
43     }
44     return a1;
45 }
46 
47 int main(){
48     while(cin >> n){
49         for(int i = 0; i < n; i++){
50             cin >> m[i];cin >> a[i];
51         }
52         ll ans = china(n);
53         ll sum = 0;
54         cout << ans <<endl;
55     }
56     return 0;
57 }

Poj2891

  1 //Hysbz1588 Splay模板
  2 //模板https://files.cnblogs.com/files/tony-/Splay%E5%9F%BA%E7%A1%80_%E6%A8%A1%E6%9D%BF.pdf
  3 #include <iostream>
  4 #include <cmath>
  5 #define l(x) ch[x][0]
  6 #define r(x) ch[x][1]
  7 #define N 33000
  8 
  9 using namespace std;
 10 int tot, rt;
 11 int ch[N][2], pre[N], key[N], rev[N];
 12 //    儿子     父亲 节点值  翻转标记
 13 
 14 void init(int n){
 15     rt = tot = 0;
 16     l(rt)=r(rt)=pre[rt]=key[rt]=0;
 17 }
 18 
 19 void newnode(int &u, int fa, int val){
 20     u = ++tot;
 21     l(u) = r(u) = 0;
 22     pre[u] = fa;
 23     key[u] = val;
 24 }
 25 
 26 void rotate(int u, int dir){//dir=1是右旋
 27     int fa = pre[u];
 28     ch[fa][!dir] = ch[u][dir];//父亲的儿子位置更新
 29     pre[ch[u][dir]] = fa;//更新原来的儿子的父亲
 30     if(pre[fa])//如果父节点不是根节点，则更新爷爷的儿子
 31         ch[pre[fa]][ch[pre[fa]][1]==fa]=u;
 32     pre[u] = pre[fa];//更新u的父亲
 33     ch[u][dir] = fa;//更新u的儿子的父亲    
 34     pre[fa] = u;//更新u的父亲的父亲
 35 }
 36 
 37 void splay(int u, int goal){//将节点u旋转为goal的儿子
 38     int fa, kind;
 39     while(pre[u] != goal){
 40         if(pre[pre[u]] == goal){//爷爷是目标，只旋转一次
 41             rotate(u, l(pre[u])==u);
 42         }else{
 43             fa = pre[u];
 44             int dir = l(pre[fa])==fa;
 45             if(ch[fa][dir]==u){//一左一右，两次方向相反的旋转
 46                 rotate(u,!dir);
 47                 rotate(u,dir);
 48             }else{//同左同右，先转父亲
 49                 rotate(fa,dir);
 50                 rotate(u,dir);
 51             }
 52         }
 53     }
 54     if(goal==0)
 55         rt = u;
 56 }
 57 
 58 int insert(int val){//插入val，将此节点旋转为根
 59     if(!rt)
 60         newnode(rt,0,val);
 61     else{
 62         int x = rt;
 63         while(ch[x][key[x]<val]){//根的值小于val
 64             if(key[x] == val){
 65                 splay(x,0);
 66                 return 0;
 67             }
 68             x = ch[x][key[x]<val];//val>当前节点 进入右儿子，反之xxxx
 69         }
 70         newnode(ch[x][key[x]<val], x, val);
 71         splay(ch[x][key[x]<val], 0);
 72     }
 73     return 1;
 74 }
 75 
 76 int getpre(int u){
 77     u = l(u);
 78     while(r(u)){
 79         u=r(u);
 80     }
 81     return u;
 82 }
 83 
 84 int getnxt(int u){
 85     u = r(u);
 86     while(l(u)){
 87         u=l(u);
 88     }
 89     return u;
 90 }
 91 
 92 int main(){
 93     int a;
 94     int n;
 95     cin >> n;
 96     init(n);
 97     insert(-0x3f3f3f3f);//插入两个无限大小的点，才可以比较大小
 98     insert(0x3f3f3f3f);
 99     cin >> a;
100     insert(a);
101     int sum = a;
102     for(int i = 1; i < n; i++){
103         cin >> a;
104         if(insert(a))
105             sum += min(a-key[getpre(rt)], key[getnxt(rt)]-a);//a已经转为根，直接找rt的pre和next
106         //cout<<"i="<<i <<" "<<sum <<" "<<key[getpre(rt)]<<" "<<key[getnxt(rt)]<<endl;
107     }
108     cout << sum <<endl;
109     return 0;
110 }

Hysbz1588

  1 //Hdu1754 splay单点修改，区间查询
  2 //https://files.cnblogs.com/files/tony-/Splay%E5%9F%BA%E7%A1%80_%E6%A8%A1%E6%9D%BF.pdf
  3 #include <iostream>
  4 #include <stdio.h>
  5 #include <algorithm>
  6 #include <cstring>
  7 #define l(x) ch[x][0]
  8 #define r(x) ch[x][1]
  9 using namespace std;
 10 
 11 #define INF 0x3f3f3f3f
 12 #define ll long long
 13 #define l(x) ch[x][0]
 14 #define r(x) ch[x][1]
 15 #define keytree ch[ch[rt][1]][0]
 16 #define N 200010
 17 
 18 int rt, tot;
 19 int key[N],ch[N][2], pre[N], p[N],  cnt[N],    maxi[N],     siz[N];
 20 //  结点的值 儿子    父亲 数组的值 本结点规模 子树最大值 包含自身的子树大小
 21 
 22 void inline push_up(int u){
 23     siz[u] = siz[l(u)] + siz[r(u)] + cnt[u];
 24     maxi[u] = max(max(maxi[l(u)],maxi[r(u)]), key[u]);
 25 }
 26 
 27 int inline getkth(int u, int k){
 28     int s = siz[l(u)];
 29     if(s==k)
 30         return u;
 31     if(s>k)
 32         return getkth(l(u), k);
 33     return getkth(r(u), k-s-1);
 34 }
 35 
 36 void inline rotate(int u, int dir){//dir=1是右旋
 37     int fa = pre[u];
 38     ch[fa][!dir] = ch[u][dir];
 39     pre[ch[u][dir]] = fa;
 40     if(pre[fa]){
 41         int son = ch[pre[fa]][1]==fa;
 42         ch[pre[fa]][son] = u;
 43     }
 44     pre[u] = pre[fa];
 45     ch[u][dir] = fa;   
 46     pre[fa] = u;
 47     push_up(fa);
 48 }
 49 
 50 void inline splay(int u, int goal){//将节点u旋转为goal的儿子
 51     while(pre[u] != goal){
 52         if(pre[pre[u]] == goal){//爷爷是目标，只旋转一次
 53             rotate(u, l(pre[u])==u);
 54         }else{
 55             int fa, dir;
 56             fa = pre[u];
 57             dir = l(pre[fa]) == fa;//左儿子1，右儿子0
 58             if(ch[fa][dir] == u){//一左一右，两次方向相反的旋转
 59                 rotate(u, !dir);
 60                 rotate(u,dir);
 61             }else{//同左同右，先转父亲
 62                 rotate(fa, dir);
 63                 rotate(u, dir);
 64             }
 65         }
 66     }
 67     push_up(u);
 68     if(goal == 0)
 69         rt = u;
 70 }
 71 
 72 int inline query(int l, int r){
 73     splay(getkth(rt,l-1), 0);
 74     splay(getkth(rt,r+1), rt);
 75     return maxi[keytree];
 76 }
 77 
 78 void inline update(int k,int val){
 79     int u = getkth(rt, k);
 80     splay(u, 0);
 81     key[u] = val;
 82     push_up(u);
 83 }
 84 
 85 void inline newnode(int &u, int fa, int val){
 86     u = ++tot;
 87     l(u) = r(u) = 0;
 88     pre[u] = fa;
 89     siz[u] = cnt[u] = 1;
 90     key[u] = maxi[u] = val;
 91 }
 92 
 93 void inline build(int &u, int l, int r, int fa){
 94     if(l>r)
 95         return;
 96     int mid = (l+r)>>1;
 97     newnode(u, fa, p[mid]);
 98     build(l(u), l, mid-1, u);
 99     build(r(u), mid+1, r, u);
100     push_up(u);
101 }
102 
103 void inline init(int n){
104     rt = tot = 0;
105     l(rt) = r(rt) = pre[rt] = siz[rt] = cnt[rt] = 0;
106     key[rt] = maxi[rt] = -1;
107     newnode(rt,0,-1);//插入两个虚点
108     newnode(r(rt),rt,-1);
109     build(keytree, 1, n, r(rt));
110     push_up(r(rt));
111     push_up(rt);
112 }
113 
114 int main() {
115     int n, m;
116     while(~scanf("%d%d", &n, &m)){
117         for(int i = 1; i <= n; i++)
118             scanf("%d",&p[i]);
119         init(n);
120         char sh[2];
121         while(m--){
122             scanf("%s",sh);
123             if(sh[0]=='Q'){
124                 int l, r;
125                 scanf("%d%d",&l, &r);
126                 cout << query(l, r) << endl;
127             }else{
128                 int k, val;
129                 scanf("%d%d",&k, &val);
130                 update(k, val);
131             }
132         }
133     }
134     return 0;
135 }

Hdu1754

  1 //Poj3468 区间修改，区间查询
  2 #include <iostream>
  3 #include <stdio.h>
  4 #include <algorithm>
  5 #include <cstring>
  6 #define l(x) ch[x][0]
  7 #define r(x) ch[x][1]
  8 using namespace std;
  9 
 10 #define INF 0x3f3f3f3f
 11 #define ll long long
 12 #define l(x) ch[x][0]
 13 #define r(x) ch[x][1]
 14 #define keytree ch[ch[rt][1]][0]
 15 #define N 100010
 16 
 17 int rt, tot;
 18 ll sum[N];//延迟更新 子树结点和
 19 int add[N],  key[N],  ch[N][2], pre[N], p[N],   siz[N];
 20 // 要更新的值 结点的值  儿子    父亲 数组的值 本结点规模 
 21 
 22 void inline push_up(int u){
 23     siz[u] = siz[l(u)] + siz[r(u)] + 1;
 24     sum[u] = sum[l(u)] + sum[r(u)] + key[u] + add[u];
 25 }
 26 
 27 void push_down(int u){
 28     if(add[u]){//将延迟标记更新到孩子结点
 29         key[u] += add[u];
 30         add[l(u)] += add[u];
 31         add[r(u)] += add[u];
 32         sum[l(u)] += 1ll*add[u]*siz[l(u)];
 33         sum[r(u)] += 1ll*add[u]*siz[r(u)];
 34         add[u] = 0;
 35     }
 36 }
 37 
 38 int inline getkth(int u, int k){//获取第k位,u是根
 39     push_down(u);
 40     int s = siz[l(u)];
 41     if(s==k)
 42         return u;
 43     if(s>k)
 44         return getkth(l(u), k);
 45     return getkth(r(u), k-s-1);
 46 }
 47 
 48 void inline rotate(int u, int dir){//dir=1是右旋
 49     int fa = pre[u];
 50     ch[fa][!dir] = ch[u][dir];
 51     pre[ch[u][dir]] = fa;
 52     if(pre[fa]){
 53         int son = ch[pre[fa]][1]==fa;
 54         ch[pre[fa]][son] = u;
 55     }
 56     pre[u] = pre[fa];
 57     ch[u][dir] = fa;
 58     pre[fa] = u;
 59     push_up(fa);
 60 }
 61 
 62 void inline splay(int u, int goal){//将节点u旋转为goal的儿子
 63     push_down(u);
 64     while(pre[u] != goal){
 65         int fa, dir;
 66         fa = pre[u];
 67         if(pre[fa] == goal){//爷爷是目标，只旋转一次
 68             push_down(fa);
 69             push_down(u);
 70             rotate(u, l(fa)==u);
 71         }else{
 72             push_down(pre[fa]);
 73             push_down(fa);
 74             push_down(u);
 75             dir = l(pre[fa])==fa;//左儿子1，右儿子0
 76             if(ch[fa][dir] == u){//一左一右，两次方向相反的旋转
 77                 rotate(u, !dir);
 78                 rotate(u,dir);
 79             }else{//同左同右，先转父亲
 80                 rotate(fa, dir);
 81                 rotate(u, dir);
 82             }
 83         }
 84     }
 85     push_up(u);
 86     if(goal == 0)
 87         rt = u;
 88 }
 89 
 90 ll inline query(int l, int r){
 91     splay(getkth(rt,l-1), 0);
 92     splay(getkth(rt,r+1), rt);
 93     return sum[keytree];
 94 }
 95 
 96 void inline update(int l, int r,int val){
 97     splay(getkth(rt,l-1), 0);
 98     splay(getkth(rt,r+1), rt);
 99     add[keytree] += val;
100     sum[keytree] += siz[keytree]*val;
101 }
102 
103 void inline newnode(int &u, int fa, int val){
104     u = ++tot;
105     l(u) = r(u) = 0;
106     pre[u] = fa;
107     siz[u] = 1;
108     key[u] = sum[u] = val;
109     add[u] = 0;
110 }
111 
112 void inline build(int &u, int l, int r, int fa){
113     if(l>r)//建树 中间结点先建立 然后分别对区间两端在左右子树建立
114         return;
115     int mid = (l+r)>>1;
116     newnode(u, fa, p[mid]);
117     build(l(u), l, mid-1, u);
118     build(r(u), mid+1, r, u);
119     push_up(u);
120 }
121 
122 void inline init(int n){
123     rt = tot = 0;
124     l(rt) = r(rt) = pre[rt] = siz[rt] = 0;
125     add[rt] = sum[rt] = 0;
126     newnode(rt, 0, -1);//插入两个虚点
127     newnode(r(rt), rt, -1);
128     siz[rt] = 2;
129 }
130 
131 int main() {
132     int n, m;
133     while(~scanf("%d%d", &n, &m)){
134         for(int i = 1; i <= n; i++)
135             scanf("%d",&p[i]);
136         init(n);
137         build(keytree, 1, n, r(rt));
138         push_up(r(rt));
139         push_up(rt);
140         char sh[2];
141         while(m--){
142             scanf("%s",sh);
143             int l, r, val;
144             if(sh[0]=='Q'){
145                 scanf("%d%d",&l, &r);
146                 cout << query(l, r) << endl;
147             }else{
148                 scanf("%d%d%d", &l, &r, &val);
149                 update(l, r, val);
150             }
151         }
152     }
153     return 0;
154 }

Poj3468

  1 //Hdu1890 splay区间翻转
  2 #include <iostream>
  3 #include <stdio.h>
  4 #include <algorithm>
  5 #include <cstring>
  6 #define l(x) ch[x][0]
  7 #define r(x) ch[x][1]
  8 using namespace std;
  9 
 10 #define INF 0x3f3f3f3f
 11 #define ll long long
 12 #define l(x) ch[x][0]
 13 #define r(x) ch[x][1]
 14 #define keytree ch[ch[rt][1]][0]
 15 #define N 100010
 16 
 17 struct g{
 18     int num, id;
 19     bool operator < (const g c) const{
 20         if(num==c.num) return id<c.id;
 21         return num < c.num;
 22     }
 23 }p[N];
 24 
 25 int rt, tot, id[N], mini[N];//子树的最小值
 26 int key[N],  ch[N][2], pre[N],  siz[N], flip[N];
 27 // 结点的值  儿子    父亲  本结点规模  是否翻转
 28 
 29 void inline push_up(int u){
 30     siz[u] = siz[l(u)] + siz[r(u)] + 1;
 31     mini[u] = min(key[u], min(mini[l(u)], mini[r(u)]));
 32 }
 33 
 34 void push_down(int u){//延迟更新，翻转
 35     if(flip[u]){
 36         if(l(u))
 37             flip[l(u)] ^= 1;
 38         if(r(u))
 39             flip[r(u)] ^= 1;
 40         swap(l(u), r(u));
 41         flip[u] = 0;
 42     }
 43 }
 44 
 45 int inline getkth(int u, int k){//获取第k位,u是根
 46     push_down(u);
 47     int s = siz[l(u)] + 1;
 48     if(s==k)
 49         return u;
 50     if(s>k)
 51         return getkth(l(u), k);
 52     return getkth(r(u), k-s);
 53 }
 54 
 55 void inline rotate(int u, int dir){//dir=1是右旋
 56     int fa = pre[u];
 57     ch[fa][!dir] = ch[u][dir];
 58     pre[ch[u][dir]] = fa;
 59     if(pre[fa]){
 60         int son = ch[pre[fa]][1]==fa;
 61         ch[pre[fa]][son] = u;
 62     }
 63     pre[u] = pre[fa];
 64     ch[u][dir] = fa;
 65     pre[fa] = u;
 66     push_up(fa);
 67 }
 68 
 69 void inline splay(int u, int goal){//将节点u旋转为goal的儿子
 70     push_down(u);
 71     while(pre[u] != goal){
 72         int fa, dir;
 73         fa = pre[u];
 74         if(pre[fa] == goal){//爷爷是目标，只旋转一次
 75             push_down(fa);
 76             push_down(u);
 77             rotate(u, l(fa)==u);
 78         }else{
 79             push_down(pre[fa]);
 80             push_down(fa);
 81             push_down(u);
 82             dir = l(pre[fa])==fa;//左儿子1，右儿子0
 83             if(ch[fa][dir] == u){//一左一右，两次方向相反的旋转
 84                 rotate(u, !dir);
 85                 rotate(u,dir);
 86             }else{//同左同右，先转父亲
 87                 rotate(fa, dir);
 88                 rotate(u, dir);
 89             }
 90         }
 91     }
 92     push_up(u);
 93     if(goal == 0)
 94         rt = u;
 95 }
 96 
 97 int getpre(int u){//求u的前驱
 98     push_down(u);
 99     u = l(u);
100     push_down(u);
101     while(r(u)){
102         u = r(u);
103         push_down(u);
104     }
105     return u;
106 }
107 
108 void del(int u){//旋转到根然后删去
109     splay(getkth(rt, u), 0);
110     if(l(rt)){
111         int i = getpre(rt);
112         splay(i, rt);
113         r(i) = r(rt);
114         pre[r(rt)] = i;
115         rt = l(rt);
116         pre[rt] = 0;
117         push_up(rt);
118     }else{
119         rt = r(rt);
120         pre[rt] = 0;
121     }
122 }
123 
124 void inline newnode(int &u, int fa, int val){
125     u = ++tot;
126     l(u) = r(u) = 0;
127     pre[u] = fa;
128     siz[u] = 1;
129     mini[u] = key[u] = val;
130     flip[u] = 0;
131 }
132 
133 void inline build(int &u, int l, int r, int fa){
134     if(l>r)//建树 中间结点先建立 然后分别对区间两端在左右子树建立
135         return;
136     int mid = (l+r)>>1;
137     newnode(u, fa, id[mid]);
138     build(l(u), l, mid-1, u);
139     build(r(u), mid+1, r, u);
140     push_up(u);
141 }
142 
143 void inline init(int n){
144     rt = tot = 0;
145     l(rt) = r(rt) = pre[rt] = siz[rt] = flip[rt] = 0;
146     key[rt] = mini[rt] = N;
147     newnode(rt, 0, INF);//插入两个虚点
148     newnode(r(rt), rt, INF);
149     build(keytree, 1, n, r(rt));
150     push_up(r(rt));
151     push_up(rt);
152 }
153 
154 int getmin(int u, int x){//求子树的最小值
155     push_down(u);
156     if(key[u] == x)
157         return 1 + siz[l(u)];
158     if(mini[l(u)] == x)
159         return getmin(l(u),x);
160     if(mini[r(u)] == x)
161         return siz[l(u)]+getmin(r(u),x)+1;
162 }
163 
164 int main() {
165     int n;
166     while(~scanf("%d", &n) && n){
167         for(int i = 1; i <= n; i++){
168             scanf("%d",&p[i].num);
169             p[i].id = i;
170         }
171         sort(p+1, p+n+1);
172         for(int i = 1; i <= n; i++)
173             id[p[i].id] = i;//重新做个标记
174         init(n);
175         for(int i = 1; i < n; i++){
176             int ans = getmin(rt, i);//找到值i的位置
177             cout << ans+i-2;
178             if(i<n)
179                 cout << " ";
180             splay(getkth(rt,1), 0);
181             splay(getkth(rt,ans), rt);
182             flip[keytree] ^= 1;
183             del(ans);
184         }cout << n << endl;
185     }
186     return 0;
187 }

Hdu1890

  1 //Hysbz1269 splay区间旋转
  2 #include <iostream>
  3 #include <stdio.h>
  4 #include <algorithm>
  5 #include <cstring>
  6 #define l(x) ch[x][0]
  7 #define r(x) ch[x][1]
  8 using namespace std;
  9 
 10 #define INF 0x3f3f3f3f
 11 #define ll long long
 12 #define l(x) ch[x][0]
 13 #define r(x) ch[x][1]
 14 #define keytree ch[ch[rt][1]][0]
 15 #define N 2*1024*1024+2
 16 
 17 char sh[N];
 18 int pos;
 19 int rt, tot;
 20 int key[N],  ch[N][2], pre[N],  siz[N], flip[N];
 21 // 结点的值  儿子    父亲  本结点规模  是否翻转
 22 
 23 void visit(int u){//for test
 24     if(!u) return;
 25     visit(l(u));
 26     printf("u:%d lch:%d rch:%d key:%c pos:%d
",u,l(u),r(u),key[u],pos);
 27     visit(r(u));
 28 }
 29 
 30 void push_up(int u){
 31     siz[u] = siz[l(u)] + siz[r(u)] + 1;
 32 }
 33 
 34 void push_down(int u){//延迟更新，翻转
 35     if(flip[u]){
 36         flip[l(u)] ^= 1;
 37         flip[r(u)] ^= 1;
 38         swap(l(u), r(u));
 39         flip[u] = 0;
 40     }
 41 }
 42 
 43 void rotate(int u, int dir){//dir=1是右旋
 44     int fa = pre[u];
 45     ch[fa][!dir] = ch[u][dir];
 46     pre[ch[u][dir]] = fa;
 47     if(pre[fa]){
 48         int son = ch[pre[fa]][1]==fa;
 49         ch[pre[fa]][son] = u;
 50     }
 51     pre[u] = pre[fa];
 52     ch[u][dir] = fa;
 53     pre[fa] = u;
 54     push_up(fa);
 55 }
 56 
 57 void splay(int u, int goal){//将节点u旋转为goal的儿子
 58     push_down(u);
 59     while(pre[u] != goal){
 60         int fa, dir;
 61         fa = pre[u];
 62         if(pre[fa] == goal){//爷爷是目标，只旋转一次
 63             push_down(fa);
 64             push_down(u);
 65             rotate(u, l(fa)==u);
 66         }else{
 67             push_down(pre[fa]);
 68             push_down(fa);
 69             push_down(u);
 70             dir = l(pre[fa])==fa;//左儿子1，右儿子0
 71             if(ch[fa][dir] == u){//一左一右，两次方向相反的旋转
 72                 rotate(u, !dir);
 73                 rotate(u,dir);
 74             }else{//同左同右，先转父亲
 75                 rotate(fa, dir);
 76                 rotate(u, dir);
 77             }
 78         }
 79     }
 80     push_up(u);
 81     if(goal == 0)
 82         rt = u;
 83 }
 84 
 85 int getkth(int u, int t){//获取第t位,u是根
 86     push_down(u);
 87     int s = siz[l(u)];
 88     if(s==t)
 89         return u;
 90     if(s>t)
 91         return getkth(l(u),t);
 92     return getkth(r(u), t-s-1);
 93 }
 94 
 95 void insert(int u, int x){//插入x到k尾部
 96     splay(getkth(rt,u), 0);
 97     splay(getkth(rt,u+1), rt);
 98     pre[x] = r(rt);
 99     keytree = x;
100     push_up(r(rt));
101     push_up(rt);
102 }
103 
104 void newnode(int &u, int fa, int val){
105     u = ++tot;
106     l(u) = r(u) = 0;
107     pre[u] = fa;
108     siz[u] = 1;
109     flip[u] = 0;
110     key[u] = val;
111 }
112 
113 void build(int &u, int l, int r, int fa){
114     if(l > r) return;
115     int mid = (l+r)>>1;
116     newnode(u,fa,(int)sh[mid]);
117     build(l(u),l,mid-1,u);
118     build(r(u),mid+1,r,u);
119     push_up(u);
120 }
121 
122 void init(){
123     rt = tot = 0;
124     key[rt] = l(rt) = r(rt) = pre[rt] = siz[rt] = flip[rt] = 0;
125     newnode(rt, 0, -1);//插入两个虚点
126     newnode(r(rt), rt, -1);
127     push_up(r(rt));
128     push_up(rt);
129 }
130 
131 void del(int u, int p){
132     splay(getkth(rt,u), 0);
133     splay(getkth(rt,u+p+1), rt);
134     keytree = 0;
135     push_up(r(rt));
136     push_up(rt);
137 }
138 
139 void flipp(int u, int p){
140     splay(getkth(rt, u), 0);
141     splay(getkth(rt, u+p+1), rt);
142     flip[keytree] ^= 1;
143 }
144 
145 int got(int p){
146     splay(getkth(rt, p+1), 0);
147     return key[rt];
148 }
149 
150 int main() {
151     int t;
152     scanf("%d",&t);
153     pos = 0;//初始光标位置
154     init();
155     while(t--){
156         char q[20];
157         scanf("%s",q);
158         int n;
159         if(q[0]=='M'){//move
160             scanf("%d",&pos);
161         }else if(q[0]=='I'){//insert
162             scanf("%d",&n);
163             getchar();
164             gets(sh);
165             int newrt = 0;
166             build(newrt, 0, n-1, 0);
167             insert(pos, newrt);
168         }else if(q[0]=='D'){//delete
169             scanf("%d",&n);
170             del(pos,n);
171         }else if(q[0]=='R'){//rotate
172             scanf("%d",&n);
173             flipp(pos, n);
174         }else if(q[0]=='G'){//get
175             printf("!!!!!!!%c!!!!!!!!
", got(pos));
176         }else if(q[0]=='P'){//prev
177             pos--;
178         }else if(q[0]=='N'){//next
179             pos++;
180         }   
181         //visit(rt);
182     }
183     return 0;
184 }

Hysbz1269

  1 //Hysbz3223 splay区间翻转 裸
  2 #include <iostream>
  3 #include <stdio.h>
  4 #include <algorithm>
  5 #include <cstring>
  6 #define l(x) ch[x][0]
  7 #define r(x) ch[x][1]
  8 using namespace std;
  9 
 10 #define INF 0x3f3f3f3f
 11 #define ll long long
 12 #define l(x) ch[x][0]
 13 #define r(x) ch[x][1]
 14 #define keytree ch[ch[rt][1]][0]
 15 #define N 100010
 16 
 17 int rt, tot, id[N];//子树的最小值
 18 int key[N],  ch[N][2], pre[N],  siz[N], flip[N];
 19 // 结点的值  儿子    父亲  本结点规模  是否翻转
 20 
 21 void inline push_up(int u){
 22     siz[u] = siz[l(u)] + siz[r(u)] + 1;
 23 }
 24 
 25 void push_down(int u){//延迟更新，翻转
 26     if(flip[u]){
 27         flip[l(u)] ^= 1;
 28         flip[r(u)] ^= 1;
 29         swap(l(u), r(u));
 30         flip[u] = 0;
 31     }
 32 }
 33 
 34 int inline getkth(int u, int k){//获取第k位,u是根
 35     push_down(u);
 36     int s = siz[l(u)];
 37     if(s==k)
 38         return u;
 39     if(s>k)
 40         return getkth(l(u), k);
 41     return getkth(r(u), k-s-1);
 42 }
 43 
 44 void inline rotate(int u, int dir){//dir=1是右旋
 45     int fa = pre[u];
 46     ch[fa][!dir] = ch[u][dir];
 47     pre[ch[u][dir]] = fa;
 48     if(pre[fa]){
 49         int son = ch[pre[fa]][1]==fa;
 50         ch[pre[fa]][son] = u;
 51     }
 52     pre[u] = pre[fa];
 53     ch[u][dir] = fa;
 54     pre[fa] = u;
 55     push_up(fa);
 56 }
 57 
 58 void inline splay(int u, int goal){//将节点u旋转为goal的儿子
 59     push_down(u);
 60     while(pre[u] != goal){
 61         int fa, dir;
 62         fa = pre[u];
 63         if(pre[fa] == goal){//爷爷是目标，只旋转一次
 64             push_down(fa);
 65             push_down(u);
 66             rotate(u, l(fa)==u);
 67         }else{
 68             push_down(pre[fa]);
 69             push_down(fa);
 70             push_down(u);
 71             dir = l(pre[fa])==fa;//左儿子1，右儿子0
 72             if(ch[fa][dir] == u){//一左一右，两次方向相反的旋转
 73                 rotate(u, !dir);
 74                 rotate(u,dir);
 75             }else{//同左同右，先转父亲
 76                 rotate(fa, dir);
 77                 rotate(u, dir);
 78             }
 79         }
 80     }
 81     push_up(u);
 82     if(goal == 0)
 83         rt = u;
 84 }
 85 
 86 void inline newnode(int &u, int fa, int val){
 87     u = ++tot;
 88     l(u) = r(u) = 0;
 89     pre[u] = fa;
 90     siz[u] = 1;
 91     key[u] = val;
 92     flip[u] = 0;
 93 }
 94 
 95 void inline build(int &u, int l, int r, int fa){
 96     if(l>r)//建树 中间结点先建立 然后分别对区间两端在左右子树建立
 97         return;
 98     int mid = (l+r)>>1;
 99     newnode(u, fa, id[mid]);
100     build(l(u), l, mid-1, u);
101     build(r(u), mid+1, r, u);
102     push_up(u);
103 }
104 
105 void init(int n){
106     rt = tot = 0;
107     l(rt) = r(rt) = pre[rt] = siz[rt] = flip[rt] = 0;
108     key[rt] = N;
109     newnode(rt, 0, INF);//插入两个虚点
110     newnode(r(rt), rt, INF);
111     build(keytree, 1, n, r(rt));
112     push_up(r(rt));
113     push_up(rt);
114 }
115 
116 void out(int x){
117     if(!x) return;
118     push_down(x);
119     out(l(x));
120     if(key[x]!=INF)
121         printf("%d ",key[x]);
122     out(r(x));
123 }
124 
125 int main() {
126     int n, m;
127     scanf("%d%d", &n, &m);
128     for(int i = 1; i <= n; i++)
129         id[i] = i;
130     init(n);
131 
132     for(int i = 0; i < m; i++){
133         int l, r;
134         scanf("%d%d", &l, &r);
135         splay(getkth(rt,l-1),0);
136         splay(getkth(rt,r+1),rt);
137         flip[keytree] ^= 1;
138         //cout<< rt<<" "<<id[rt]<<endl;
139     }
140     out(rt);
141     return 0;
142 }

Hysbz3223

  1 //Hysbz3224 splay
  2 #include <iostream>
  3 #include <stdio.h>
  4 #include <algorithm>
  5 #include <cstring>
  6 #define l(x) ch[x][0]
  7 #define r(x) ch[x][1]
  8 using namespace std;
  9 
 10 #define INF 0x3f3f3f3f
 11 #define ll long long
 12 #define l(x) ch[x][0]
 13 #define r(x) ch[x][1]
 14 #define keytree ch[ch[rt][1]][0]
 15 #define N 100002
 16 
 17 int rt, tot;
 18 int key[N],  ch[N][2], pre[N], siz[N], cnt[N];
 19 // 结点的值  儿子     父亲  本结点规模
 20 
 21 void visit(int u){//for test
 22     if(!u) return;
 23     visit(l(u));
 24     printf("u:%d lch:%d rch:%d key:%c
",u,l(u),r(u),key[u]);
 25     visit(r(u));
 26 }
 27 
 28 int getpre(int u){
 29     u = l(u);
 30     while(r(u)){
 31         u=r(u);
 32     }
 33     return u;
 34 }
 35 
 36 int getnxt(int u){
 37     u = r(u);
 38     while(l(u)){
 39         u=l(u);
 40     }
 41     return u;
 42 }
 43 
 44 void push_up(int u){
 45     siz[u] = siz[l(u)] + siz[r(u)] + cnt[u];
 46 }
 47 
 48 void rotate(int u, int dir){//dir=1是右旋
 49     int fa = pre[u];
 50     ch[fa][!dir] = ch[u][dir];
 51     pre[ch[u][dir]] = fa;
 52     if(pre[fa]){
 53         int son = ch[pre[fa]][1]==fa;
 54         ch[pre[fa]][son] = u;
 55     }
 56     pre[u] = pre[fa];
 57     ch[u][dir] = fa;
 58     pre[fa] = u;
 59     push_up(fa);
 60 }
 61 
 62 void inline splay(int u, int goal){//将节点u旋转为goal的儿子
 63     while(pre[u] != goal){
 64         if(pre[pre[u]] == goal){//爷爷是目标，只旋转一次
 65             rotate(u, l(pre[u])==u);
 66         }else{
 67             int fa, dir;
 68             fa = pre[u];
 69             dir = l(pre[fa]) == fa;//左儿子1，右儿子0
 70             if(ch[fa][dir] == u){//一左一右，两次方向相反的旋转
 71                 rotate(u, !dir);
 72                 rotate(u,dir);
 73             }else{//同左同右，先转父亲
 74                 rotate(fa, dir);
 75                 rotate(u, dir);
 76             }
 77         }
 78     }
 79     push_up(u);
 80     if(goal == 0)
 81         rt = u;
 82 }
 83 
 84 void newnode(int &u, int fa, int val){
 85     u = ++tot;
 86     l(u) = r(u) = 0;
 87     pre[u] = fa;
 88     siz[u] = cnt[u] = 1;
 89     key[u] = val;
 90 }
 91 
 92 void insert(int val){//插入val，将此节点旋转为根
 93     if(!rt)
 94         newnode(rt,0,val);
 95     else{
 96         int x = rt, fa = 0;
 97         while(x){
 98             if(key[x] == val){
 99                 cnt[x]++;
100                 push_up(x);
101                 push_up(fa);
102                 splay(x,0);
103                 return;
104             }
105             fa = x;
106             x = ch[x][key[x]<val];//val>当前节点 进入右儿子，反之xxxx
107         }
108         newnode(x, fa, val);//没有此结点
109         ch[fa][key[fa]<val] = x;
110         push_up(fa);
111         splay(x, 0);
112     }
113 }
114 
115 int find(int x){//查询x的排名
116     int nowrt = rt, ans = 0;
117     while(1){
118         if(x < key[nowrt])
119             nowrt = l(nowrt);
120         else{
121             ans += l(nowrt)?siz[l(nowrt)]:0;
122             if(x == key[nowrt]){
123                 splay(nowrt, 0);
124                 return ans + 1;
125             }
126             ans += cnt[nowrt];
127             nowrt = r(nowrt);
128         }
129     }
130 }
131 
132 int findx(int x){//排名为x的数
133     int nowrt = rt;
134     while(1){
135         if(l(nowrt) && x<=siz[l(nowrt)]){
136             nowrt = l(nowrt);
137         }else{
138             int ans = l(nowrt)?siz[l(nowrt)]:0;
139             ans += cnt[nowrt];
140             if(x <= ans)
141                 return key[nowrt];
142             x -= ans;
143             nowrt = r(nowrt);
144         }
145     }
146 }
147 
148 void clear(int x){
149     l(x) = r(x) = pre[x] = siz[x] = cnt[x] = 0;
150 }
151 
152 void del(int x){//cnt==1 考虑有无左右儿子的情况
153     find(x);
154     if(cnt[rt] > 1){//cnt>1
155         cnt[rt]--;
156         return ;
157     }
158     if(!l(rt) && ! r(rt)){
159         clear(rt);
160         rt = 0;
161         return;
162     }
163     if(!l(rt)){
164         int oldrt = rt;
165         rt = r(rt);
166         pre[rt] = 0;
167         clear(oldrt);
168         return;
169     }else if(!r(rt)){
170         int oldrt = rt;
171         rt = l(rt);
172         pre[rt] = 0;
173         clear(oldrt);
174         return;
175     }
176     int oldrt = rt;
177     splay(getpre(rt),0);
178     pre[r(oldrt)] = rt;
179     r(rt) = r(oldrt);
180     clear(oldrt);
181     push_up(rt);
182 }
183 
184 int main() {
185     int t;
186     scanf("%d",&t);
187     while(t--){
188         int k, n;
189         scanf("%d",&k);
190         scanf("%d",&n);
191         if(k==1){//insert
192             insert(n);
193         }else if(k==2){//delete
194             del(n);
195         }else if(k==3){//query
196             printf("%d
", find(n));
197         }else if(k==4){//query rank==n
198             printf("%d
", findx(n));
199         }else if(k==5){//prev
200             insert(n);
201             printf("%d
", key[getpre(rt)]);
202             del(n);
203         }else if(k==6){//next
204             insert(n);
205             printf("%d
", key[getnxt(rt)]);
206             del(n);
207         }
208         //visit(rt);
209     }
210     return 0;
211 }

Hysbz3224

 1 //最小边覆盖
 2 #include <stdio.h>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <string.h>
 6 #include <stdlib.h>
 7 using namespace std;
 8 
 9 int o;
10 char g[50][50];
11 int edge[50][50];
12 int a[50][50];
13 int gg[50];
14 int vis[50];
15 int n ,m;
16 int cnt, ans;
17 int xn[] = {0,1,0,-1};
18 int yn[] = {1,0,-1,0};
19 
20 void dfs(int x, int y){//cout << "now="<<x << " "<<y<<endl;
21     if(g[x][y] == '*'){
22         for(int i = 0; i < 4; i++){
23             int x1 = x+xn[i], y1 = y+yn[i];
24             if(x1>=0 && x1<n && y1>=0 && y1<m && g[x1][y1]=='*'){
25                 edge[a[x][y]][a[x1][y1]] = 1;
26             }
27         }
28     }
29 }
30 
31 int path(int u)
32 {
33     int v;
34     for(v=0; v<o; v++)
35     {
36         if(edge[u][v]&&!vis[v])
37         {
38             vis[v]=1;
39             if(gg[v]==-1||path(gg[v]))
40             {
41                 gg[v]=u;
42                 return 1;
43             }
44         }
45     }
46     return 0;
47 }
48 
49 int main(){
50     int t;
51     scanf("%d",&t);
52     while(t--){
53         ans = 1;
54         scanf("%d%d",&n,&m);
55         for(int i = 0; i < n; i++){
56             for(int j = 0; j < m; j++){
57                 scanf(" %c",&g[i][j]);
58                 if(g[i][j]=='*')
59                     a[i][j] = ans++;
60             }
61         }
62         o = ans;
63         memset(edge,0,sizeof(edge));
64         for(int i = 0; i < n; i++){
65             for(int j = 0; j < m; j++){
66                 dfs(i,j);
67             }
68         }
69         int cnt = 0;
70         memset(gg,-1,sizeof(gg));
71         for(int i=0; i<o; i++)
72         {
73             memset(vis,0,sizeof(vis));
74             cnt+=path(i);
75         }
76         cout << ans-1-cnt/2 << endl;
77     }
78     return 0;
79 }

Gdufe1460

 1 //莫队算法
 2 #include <iostream>
 3 #include <stdio.h>
 4 #include <algorithm>
 5 #include <cstring>
 6 using namespace std;
 7 
 8 int got[200010],sum[30010],ch[30010];
 9 int ans;
10 struct stu{
11     int l,r,p;
12 }node[200010];
13 
14 int cmp(stu a, stu b){
15     return a.l==b.l ? a.r<b.r : a.l<b.l;
16 }
17 
18 void add(int x){
19     if(!got[x])
20         ans++;
21     got[x]++;
22 }
23 
24 void del(int x){
25     got[x]--;
26     if(!got[x])
27         ans--;
28 }
29 
30 int main()
31 {
32     int n;
33     while(~scanf("%d",&n)){
34         for(int i = 1; i <= n; i++){
35             scanf("%d",&ch[i]);
36         }
37         int m;
38         scanf("%d",&m);
39         for(int i = 1; i <= m; i++){
40             scanf("%d%d",&node[i].l,&node[i].r);
41             node[i].p = i;
42         }
43         sort(node,node+m,cmp);
44 
45         ans = 0;
46         int l = 1, r = 0;
47         memset(got,0,sizeof(got));
48         for(int i = 1; i <= m; i++){
49             while(r < node[i].r)
50                 add(ch[++r]);
51 
52             while(l > node[i].l)
53                 add(ch[--l]);
54 
55             while(r > node[i].r)
56                 del(ch[r--]);
57 
58             while(l < node[i].l)
59                 del(ch[l++]);
60 
61             sum[node[i].p] = ans;
62         }
63         for(int i = 1; i <= m; i++){
64             printf("%d
", sum[i]);
65         }
66 
67     }
68     return 0;
69 }

GdufeOJ1465