3月27日-？

Description

Given an array with
n
integers, assume f(S) as the result of executing xor operation among all the elements of set S. e.g. if S={1,2,3} then f(S)=0.

your task is: calculate xor of all f(s), here s⊆S.

Input

This problem has multi test cases. First line contains a single integer T(T≤20) which represents the number of test cases.
For each test case, the first line contains a single integer number n(1≤n≤1,000) that represents the size of the given set. then the following line consists of n different integer numbers indicate elements(≤109) of the given set.

Output

For each test case, print a single integer as the answer.

Sample Input

1
3
1 2 3

Sample Output

In the sample，

, subsets of

, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}

Hint

题意

给你一个集合S，然后定义F(s)表示这个集合所有元素的异或和。

然后求所有S的子集的F(s)的异或和

题解：

考虑每个数的贡献，显然当n>1的时候，每个数在2^(n-1)个集合里面，所以贡献为0

当n=1的时候，答案就是x啦

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<set>
 6 #include<map>
 7 #include<queue>
 8 #include<vector>
 9 using namespace std;
10 const int maxn = 1e5;
11 typedef long long ll;
12 void input(){
13     int t,n;
14     scanf("%d",&t);
15     while(t--){
16         scanf("%d",&n);
17         int x;
18         scanf("%d",&x);
19         for(int i = 2; i<=n; i++){
20             scanf("%d",&x);
21         }
22         if(n == 1){
23             printf("%d
",x);
24         }
25         else{
26             printf("0
");
27         }
28     }
29 }
30 int main()
31 {
32     input();
33     return 0;
34 }

卷珠帘

Description

As we all known, xiaoxin is a brilliant coder. He knew palindromic strings when he was only a six grade student at elementry school.

This summer he was working at Tencent as an intern. One day his leader came to ask xiaoxin for help. His leader gave him a string and he wanted xiaoxin to generate palindromic strings for him. Once xiaoxin generates a different palindromic string, his leader will give him a watermelon candy. The problem is how many candies xiaoxin's leader needs to buy?

Input

This problem has multi test cases. First line contains a single integer T(T≤20) which represents the number of test cases.
For each test case, there is a single line containing a string S(1≤length(S)≤1,000).

Output

For each test case, print an integer which is the number of watermelon candies xiaoxin's leader needs to buy after mod 1,000,000,007.

Sample Input

3
aa
aabb
a

Sample Output

1
2
1

Hint

题意

给你一个串，你可以改变字符位置

问你能够形成多少种回文串。

题解：

高中一个元素中有重复的，A(n)/A(a1)/A(a2)……，还学习了个逆元问题

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<set>
 6 #include<map>
 7 #include<queue>
 8 #include<vector>
 9 using namespace std;
10 const int mod = 1e9+7;
11 typedef long long ll;
12 char s[1111];
13 int a[30];
14 ll quick_pow(ll a, ll b) {
15     ll ans = 1;
16     for (; b; b /= 2, a = (a * a) % mod)
17         if (b & 1) ans = (ans * a) % mod;
18     return ans;
19 }
20 
21 ll A(ll n){
22     ll sum = 1;
23     for(long long i = 1; i<=n; i++){
24         sum = (i*sum)%mod;
25     }
26     return sum;
27 }
28 void input(){
29     int t;
30     scanf("%d",&t);
31     while(t--){
32             scanf("%s",s);
33         memset(a,0,sizeof(a));
34         int len = strlen(s);
35         for(int i = 0; i<len; i++){
36             a[s[i]-'a'+1]++;
37         }
38         int count = 0;
39         ll sum = 0;
40         for(int i = 1; i<=26; i++){
41             if(a[i]%2 == 1) count++;
42             a[i]/=2;
43             sum += a[i];
44         }
45 
46         if(count>1) printf("0
");
47         else{
48             sum = A(sum);
49             for(int i = 1; i<=26; i++){
50                 sum = sum * quick_pow(A(a[i]), mod - 2) % mod;
51             }
52             printf("%I64d
",sum);
53         }
54     }
55 }
56 int main()
57 {
58     input();
59     return 0;
60 }

卷珠帘

3月28日

从训练场回来，想先去自习室写一下电路分析，结果两个小时写出半道题。。。

Problem - 1003

二分法+BFS

今天改了大半天，没改对，明天继续

  1 #include <iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<queue>
  6 const int maxn = 505;
  7 using namespace std;
  8 char maze[maxn][maxn];
  9 int vis[maxn][maxn];
 10 pair<int,int> p[maxn*maxn];
 11 int cur;
 12 int n,m;
 13 int to[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
 14 struct node{
 15     int x,y;
 16 };
 17 bool check1(int x,int y){
 18     if(maze[x][y] == '1') return false;
 19     if(x<0||y<0||y>=m) return false;
 20     if(vis[x][y]) return false;
 21     return true;
 22 }
 23 int bfs(){
 24     queue<node> q;
 25     node k,nex;
 26     memset(vis,0,sizeof(vis));
 27     k.x = 0,k.y = 0;
 28     vis[k.x][k.y] = 1;
 29     q.push(k);
 30     while(!q.empty()){
 31         k = q.front();
 32         q.pop();
 33         if(k.y>n) return 1;
 34         for(int i = 0; i<4; i++){
 35             nex.x = k.x + to[i][0];
 36             nex.y = k.y + to[i][1];
 37             if(check1(nex.x,nex.y)){
 38                 vis[nex.x][nex.y] = 1;
 39                 q.push(nex);
 40             }
 41         }
 42     }
 43     return 0;
 44 }
 45 int check(int x){
 46     if(x>cur){
 47         for(int i = cur; i<=x; i++){
 48             maze[p[i].first][p[i].second] = '1';
 49         }
 50     }
 51     else if(x<cur){
 52         for(int i = x; i<=cur; i++){
 53             maze[p[i].first][p[i].second] = '0';
 54         }
 55     }
 56     cur = x;
 57     return bfs();
 58 }
 59 void solve(){
 60     int t;
 61     scanf("%d",&t);
 62     while(t--){
 63             char c;
 64         scanf("%d%d",&n,&m);
 65         //getchar();
 66         for(int i = 0; i<m; i++) maze[0][i] = '0';
 67         for(int i = 1; i<=n; i++){
 68             scanf("%s",maze[i]);
 69         }
 70         //printf("asdas
");
 71         int q;
 72         scanf("%d",&q);
 73         for(int i = 1; i<=q; i++){
 74              scanf("%d %d",&p[i].first,&p[i].second);
 75              p[i].first++;
 76         }
 77 
 78         int low = 1,high = q;
 79         cur = 1;
 80         if(check(q)){
 81             printf("-1
");
 82 
 83             for(int i = 0;i<=n; i++){
 84                  printf("%s",maze[i]);
 85                  printf("
");
 86             }
 87             continue;
 88         }
 89         int tur = 0;
 90         while(low<=high){
 91             int mid = (low+high)>>1;
 92             int k = check(mid);
 93             printf("%d
",k);
 94             if(k){
 95                     tur = mid;
 96                 low = mid+1;
 97             }
 98             else high = mid-1;
 99 
100         }
101         printf("%d
",tur);
102     }
103 }
104 int main()
105 {
106     solve();
107     return 0;
108 }

卷珠帘

India and China Origins

Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 905 Accepted Submission(s): 311

Problem Description

A long time ago there are no himalayas between India and China, the both cultures are frequently exchanged and are kept in sync at that time, but eventually himalayas rise up. With that at first the communation started to reduce and eventually died.

Let's assume from my crude drawing that the only way to reaching from India to China or viceversa is through that grid, blue portion is the ocean and people haven't yet invented the ship. and the yellow portion is desert and has ghosts roaming around so people can't travel that way. and the black portions are the location which have mountains and white portions are plateau which are suitable for travelling. moutains are very big to get to the top, height of these mountains is infinite. So if there is mountain between two white portions you can't travel by climbing the mountain.
And at each step people can go to 4 adjacent positions.

Our archeologists have taken sample of each mountain and estimated at which point they rise up at that place. So given the times at which each mountains rised up you have to tell at which time the communication between India and China got completely cut off.

Input

There are multi test cases. the first line is a sinle integer

Output

Single line at which year the communication got cut off.

print -1 if these two countries still connected in the end.

Hint:

From the picture above, we can see that China and India have no communication since 4th year.

Sample Input

Sample Output

4

3月29日

中午午睡时改了一个小时，终于改对了，坑。。。

Problem - 1003

  1 #include <iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<queue>
  6 const int maxn = 505;
  7 using namespace std;
  8 char maze[maxn][maxn];
  9 int vis[maxn][maxn];
 10 pair<int,int> p[maxn*maxn];
 11 int cur;
 12 int n,m;
 13 int to[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
 14 struct node{
 15     int x,y;
 16 };
 17 bool check1(int x,int y){
 18     if(maze[x][y] == '1') return false;
 19     if(x<0||y<0||y>=m) return false;
 20     if(vis[x][y]) return false;
 21     return true;
 22 }
 23 int bfs(){
 24     queue<node> q;
 25     node k,nex;
 26     memset(vis,0,sizeof(vis));
 27     k.x = 0,k.y = 0;
 28     vis[k.x][k.y] = 1;
 29     q.push(k);
 30   //  printf("
");
 31     while(!q.empty()){
 32         k = q.front();
 33         q.pop();
 34         if(k.x>n){ //昨天这里写成了k.y>n......
 35        //     printf("
%d %d
",k.x,k.y);
 36              return 1;
 37         }
 38         for(int i = 0; i<4; i++){
 39             nex.x = k.x + to[i][0];
 40             nex.y = k.y + to[i][1];
 41             if(check1(nex.x,nex.y)){
 42                 //    printf("%d %d
",nex.x,nex.y);
 43                 vis[nex.x][nex.y] = 1;
 44                 q.push(nex);
 45             }
 46         }
 47     }
 48     return 0;
 49 }
 50 int check(int x){
 51     if(x>cur){
 52         for(int i = cur; i<=x; i++){
 53             maze[p[i].first][p[i].second] = '1';
 54         }
 55     }
 56     else if(x<cur){
 57         for(int i = x+1; i<=cur; i++){
 58             maze[p[i].first][p[i].second] = '0';
 59         }
 60     }
 61     cur = x;
 62     return bfs();
 63 }
 64 void solve(){
 65     int t;
 66     scanf("%d",&t);
 67     while(t--){
 68 
 69         scanf("%d%d",&n,&m);
 70         //getchar();
 71         for(int i = 0; i<m; i++) maze[0][i] = '0';
 72         for(int i = 1; i<=n; i++){
 73             scanf("%s",maze[i]);
 74         }
 75         //printf("asdas
");
 76         int q;
 77         scanf("%d",&q);
 78         for(int i = 1; i<=q; i++){
 79              scanf("%d %d",&p[i].first,&p[i].second);
 80              p[i].first++;
 81         }
 82 
 83         int low = 1,high = q;
 84         cur = 1;
 85         if(check(q)){
 86             printf("-1
");
 87 
 88           /*  for(int i = 0;i<=n; i++){
 89                  printf("%s",maze[i]);
 90                  printf("
");
 91             }*/
 92             continue;
 93         }
 94         int tur = 0;
 95         while(low<=high){
 96             int mid = (low+high)>>1;
 97             int k = check(mid);
 98           //  printf("%d
",k);
 99             if(k){
100                     tur = mid;
101                    // printf("%d
",tur);
102                 low = mid+1;
103             }
104             else high = mid-1;
105 
106         }
107        printf("%d
",tur+1);
108     }
109 }
110 int main()
111 {
112     solve();
113     return 0;
114 }

卷珠帘

今天终于两个小时做出三道电路分析题，突破历史新高！!!

晚上补最后一道dp,明天还得改。。。

3月30日

Bomber Man wants to bomb an Array.

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 471 Accepted Submission(s): 153

Problem Description

Given an array and some positions where to plant the bombs, You have to print the Total Maximum Impact.

Each Bomb has some left destruction capability

Input

There are multi test cases denote by a integer

Output

as Maximum Total Impact can be very large print the floor(1000000 * log2(Maximum Total Impact)).

Hint:
Sample 1:

Sample 2:

Sample Input

Sample Output

4643856
5169925

本来以为是n^3的复杂度，结果看了一神的解释恍然大悟，把n/m个区间上，则时间复杂度是 n* n/m * n/m = n^2/m. 枚举炸弹左右两个区间。

 1 #include <iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<queue>
 6 #include<cmath>
 7 const int maxn = 2005;
 8 using namespace std;
 9 double dp[maxn];
10 int a[maxn];
11 void solve(){
12     int t;
13     scanf("%d",&t);
14     while(t--){
15         int n,m;
16         scanf("%d%d",&n,&m);
17         for(int i = 0; i<=n; i++) dp[i] = 0.0;
18         for(int i = 1; i<=m; i++){
19             scanf("%d",&a[i]);
20             a[i]++;
21         }
22         sort(a+1,a+m+1);
23         a[m+1] = n+1;
24         for(int i = 1; i<=m; i++)
25             for(int r = a[i]; r<a[i+1]; r++)
26                 for(int l = a[i-1]+1; l<=a[i]; l++)
27                     dp[r] = max(dp[r],dp[l-1]+log2(r-l+1));
28                  //   for(int i = 0; i<=n; i++) printf("%f
",dp[i]);
29         printf("%d
",(int)floor(1e6*dp[n]));
30     }
31 }
32 int main()
33 {
34     solve();
35     return 0;
36 }

卷珠帘