题意：给出一个矩阵判断矩阵的两个对角元素是不是相同的，并且要求和其他方格中的元素不同，其他方格元素要求相同
sl:水的没边了，直接模拟过 1 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 using namespace std;
6 const int MAX =300+10 ;
7 char map[MAX][MAX];
8 int main()
9 {
10 int n;
11 while(scanf("%d",&n)==1)
12 {
13 for(int i=0;i<n;i++)
14 {
15 scanf("%s",map[i]);
16 }
17 int flag=1; char a=map[0][0]; char b=map[1][0];
18 for(int i=0;i<n;i++)
19 {
20 for(int j=0;j<n;j++)
21 {
22
23 if(i==j&&map[i][j]!=a) flag=0;
24 else if(j==n-i-1&&map[i][j]!=a) flag=0;
25 else if((map[i][j]!=b||b==a)&&i!=j&&j!=n-i-1) flag=0;
26 }
27 }
28 if(flag) printf("YES ");
29 else printf("NO ");
30 }
31 return 0;
32 }
Valera takes part in the Berland Marathon. The marathon race starts at the stadium that can be represented on the plane as a square whose lower left corner is located at point with coordinates (0, 0) and the length of the side equals a meters. The sides of the square are parallel to coordinate axes.
As the length of the marathon race is very long, Valera needs to have extra drink during the race. The coach gives Valera a bottle of drink each d meters of the path. We know that Valera starts at the point with coordinates (0, 0) and runs counter-clockwise. That is, when Valera covers a meters, he reaches the point with coordinates (a, 0). We also know that the length of the marathon race equalsnd + 0.5 meters.
Help Valera's coach determine where he should be located to help Valera. Specifically, determine the coordinates of Valera's positions when he covers d, 2·d, ..., n·d meters.
The first line contains two space-separated real numbers a and d (1 ≤ a, d ≤ 105), given with precision till 4 decimal digits after the decimal point. Number a denotes the length of the square's side that describes the stadium. Number d shows that after each d meters Valera gets an extra drink.
The second line contains integer n (1 ≤ n ≤ 105) showing that Valera needs an extra drink n times.
Print n lines, each line should contain two real numbers xi and yi, separated by a space. Numbers xi and yi in the i-th line mean that Valera is at point with coordinates (xi, yi) after he covers i·d meters. Your solution will be considered correct if the absolute or relative error doesn't exceed 10 - 4.
Note, that this problem have huge amount of output data. Please, do not use cout stream for output in this problem.
2 5
2
1.0000000000 2.0000000000
2.0000000000 0.0000000000
4.147 2.8819
6
2.8819000000 0.0000000000
4.1470000000 1.6168000000
3.7953000000 4.1470000000
0.9134000000 4.1470000000
0.0000000000 2.1785000000
0.7034000000 0.0000000000
题意:给出一个方形操场的长度，并且给出每一次能够喝水的距离确定能喝水的坐标。
sl:直接模拟即可，确定是在方形的那条边上。
1 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 using namespace std;
6 int main()
7 {
8 double a,d; int n;
9 while(scanf("%lf %lf",&a,&d)==2)
10 {
11 scanf("%d",&n);
12 double x,y; double tot=a*4; double f=0,ans,t;
13 for(int i=1;i<=n;i++)
14 {
15 t=f+d;
16 if(t>=tot)
17 {
18 int cnt=(t)/tot;
19 t-=cnt*tot;
20 }
21 if(t>=tot) t-=tot;
22 ans=t;
23 if(ans<=a) printf("%.10lf 0.0000000000 ",ans);
24 else if(ans>a&&ans<=2*a) printf("%.10lf %.10lf ",a,ans-a);
25 else if(ans>2*a&&ans<=3*a) printf("%.10lf %.10lf ",a-(ans-2*a),a);
26 else printf("0.0000000000 %.10lf ",a-(ans-3*a));
27 f=ans;
28 }
29 }
30 return 0;
31 }
Valera had an undirected connected graph without self-loops and multiple edges consisting of n vertices. The graph had an interesting property: there were at most k edges adjacent to each of its vertices. For convenience, we will assume that the graph vertices were indexed by integers from 1 to n.
One day Valera counted the shortest distances from one of the graph vertices to all other ones and wrote them out in array d. Thus, element d[i] of the array shows the shortest distance from the vertex Valera chose to vertex number i.
Then something irreparable terrible happened. Valera lost the initial graph. However, he still has the array d. Help him restore the lost graph.
The first line contains two space-separated integers n and k (1 ≤ k < n ≤ 105). Number n shows the number of vertices in the original graph. Number k shows that at most k edges were adjacent to each vertex in the original graph.
The second line contains space-separated integers d[1], d[2], ..., d[n] (0 ≤ d[i] < n). Number d[i] shows the shortest distance from the vertex Valera chose to the vertex number i.
If Valera made a mistake in his notes and the required graph doesn't exist, print in the first line number -1. Otherwise, in the first line print integer m (0 ≤ m ≤ 106) — the number of edges in the found graph.
In each of the next m lines print two space-separated integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi), denoting the edge that connects vertices with numbers ai and bi. The graph shouldn't contain self-loops and multiple edges. If there are multiple possible answers, print any of them.
3 2
0 1 1
3
1 2
1 3
3 2
4 2
2 0 1 3
3
1 3
1 4
2 3
3 1
0 0 0
-1
题意：给出一个已知节点还有其他节点到已知节点的距离数组还原这个图，满足每个点所连的边数不超过k.
sL：还是简单的模拟题（貌似cf上前三题都是模拟就可以出）直接构造一棵树即可，每次插入边的时候要记录下上个定点连了多少条边
2 #include <cstring>
3 #include <algorithm>
4 #include <vector>
5 using namespace std;
6 const int MAX = 1e5+10;
7 vector<int > G[MAX];
8 int d[MAX],vis[MAX];
9 int u[MAX],v[MAX];
10 int main()
11 {
12 int n,k,Max=-1,st;
13 while(scanf("%d %d",&n,&k)==2)
14 {
15 memset(vis,0,sizeof(vis));
16 int tot=0;
17 for(int i=1;i<=n;i++)
18 {
19 scanf("%d",&d[i]);
20 Max=max(Max,d[i]);
21 if(d[i]==0) st=i,tot++;
22 G[d[i]].push_back(i);
23 }
24
25 int flag=1,cnt,ans,cur=0;
26 for(int i=0;i<=Max;i++)
27 {
28 if(G[i].size()==0)
29 {
30 flag=0; break;
31 }
32 }
33 if(G[1].size()>k||tot!=1||!flag) printf("-1 ");
34 else
35 {
36 for(int i=1;i<=Max;i++)
37 {
38 ans=0; int m=0;
39 for(int j=0;j<G[i-1].size();j++)
40 {
41 while(m<G[i].size())
42 {
43 vis[G[i-1][j]]++;
44 if(vis[G[i-1][j]]>k) break;
45 else
46 {
47 u[cur]=G[i-1][j];
48 v[cur++]=G[i][m];
49 vis[G[i][m]]=1;
50 ans++;
51 m++;
52 }
53
54 }
55 if(ans==G[i].size()) break;
56 }
57 if(ans!=G[i].size())
58 {
59 flag=0;
60 break;
61 }
62 }
63 if(!flag) printf("-1 ");
64 else
65 {
66 printf("%d ",cur);
67 for(int i=0;i<cur;i++) printf("%d %d ",u[i],v[i]);
68 }
69 }
70 }
71 return 0;
72 }
Game "Minesweeper 1D" is played on a line of squares, the line's height is 1 square, the line's width is n squares. Some of the squares contain bombs. If a square doesn't contain a bomb, then it contains a number from 0 to 2 — the total number of bombs in adjacent squares.
For example, the correct field to play looks like that: 001*2***101*. The cells that are marked with "*" contain bombs. Note that on the correct field the numbers represent the number of bombs in adjacent cells. For example, field 2* is not correct, because cell with value 2 must have two adjacent cells with bombs.
Valera wants to make a correct field to play "Minesweeper 1D". He has already painted a squared field with width of n cells, put several bombs on the field and wrote numbers into some cells. Now he wonders how many ways to fill the remaining cells with bombs and numbers are there if we should get a correct field in the end.
The first line contains sequence of characters without spaces s1s2... sn (1 ≤ n ≤ 106), containing only characters "*", "?" and digits "0", "1" or "2". If character si equals "*", then the i-th cell of the field contains a bomb. If character si equals "?", then Valera hasn't yet decided what to put in the i-th cell. Character si, that is equal to a digit, represents the digit written in the i-th square.
Print a single integer — the number of ways Valera can fill the empty cells and get a correct field.
As the answer can be rather large, print it modulo 1000000007 (109 + 7).
?01???
4
?
2
**12
0
1
0
题意：给出一个序列，1表示旁边有1个炸弹，2表示2个，0表示旁边没有炸弹，*表示炸弹，？表示放的东西还不知道。求一共有几种方法
sl:赤裸裸的DP,可惜当时没时间做，估计要耗费我40分钟，太渣了我，dp[i][j] 表示第i为状态为j时的方案总是。
状态j分别为前一位为 0, *, *1, 1*, 2 然后扫一遍即可。
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 typedef long long ll;
6 const int MAX = 1e6+10;
7 const ll MOD = 1e9 + 7;
8
9 char str[MAX];
10 ll dp[MAX][5];
11 int main()
12 {
13 scanf("%s",str);
14 int n=strlen(str);
15 if(str[0]=='2'||str[n-1]=='2')
16 {
17 printf("0 "); return 0;
18 }
19 // 0, *, *1, 1*, 2
20 if (str[0] == '*')
21 dp[0][1] = 1;
22 else if (str[0] == '1')
23 dp[0][3] = 1;
24 else if (str[0] == '0')
25 dp[0][0] = 1;
26 else
27 dp[0][1] = dp[0][3] = dp[0][0] = 1;
28 for (int i = 1; i < n; i++)
29 {
30 if (str[i] == '0')
31 dp[i][0] = (dp[i-1][0]+dp[i-1][2]) % MOD;
32 else if (str[i] == '1')
33 {
34 dp[i][2]=dp[i-1][1];
35 dp[i][3]=(dp[i-1][0]+dp[i-1][2]) % MOD;
36 }
37 else if (str[i]=='2')
38 dp[i][4] = dp[i-1][1];
39 else if (str[i]=='*')
40 dp[i][1] = (dp[i-1][1]+dp[i-1][3]+dp[i-1][4])%MOD;
41 else
42 {
43 dp[i][0] = (dp[i-1][0]+dp[i - 1][2])%MOD;
44 dp[i][2] = dp[i-1][1];
45 dp[i][3] = (dp[i-1][0]+dp[i - 1][2])%MOD;
46 dp[i][4] = dp[i-1][1];
47 dp[i][1] = (dp[i-1][1]+dp[i - 1][3]+dp[i - 1][4]) % MOD;
48 }
49
50 }
51 int ans=(dp[n - 1][0] + dp[n - 1][1] + dp[n - 1][2]) % MOD;
52 printf("%d ",ans);
53 return 0;
54 }
Valera has a strip infinite in both directions and consisting of cells. The cells are numbered by integers. The cell number 0 has a robot.
The robot has instructions — the sequence of moves that he must perform. In one move, the robot moves one cell to the left or one cell to the right, according to instructions. Before the robot starts moving, Valera puts obstacles in some cells of the strip, excluding cell number 0. If the robot should go into the cell with an obstacle according the instructions, it will skip this move.
Also Valera indicates the finish cell in which the robot has to be after completing the entire instructions. The finishing cell should be different from the starting one. It is believed that the robot completed the instructions successfully, if during the process of moving he visited the finish cell exactly once — at its last move. Moreover, the latter move cannot be skipped.
Let's assume that k is the minimum number of obstacles that Valera must put to make the robot able to complete the entire sequence of instructions successfully and end up in some finishing cell. You need to calculate in how many ways Valera can choose k obstacles and the finishing cell so that the robot is able to complete the instructions successfully.
The first line contains a sequence of characters without spaces s1s2... sn (1 ≤ n ≤ 106), consisting only of letters "L" and "R". If character si equals "L", then the robot on the i-th move must try to move one cell to the left. If the si-th character equals "R", then the robot on the i-th move must try to move one cell to the right.
Print a single integer — the required number of ways. It's guaranteed that this number fits into 64-bit signed integer type.
RR
1
RRL
1
题意：给出一个机器指令命令机器人行动，使机器人走到最后的位置，最后的位置满足在行走的过程中只被访问过一次。当机器人碰到石头后经跳过该命令，求一共有多少
种方法放石子。
sl:只知道最多放1科石子，还有什么二分枚举之类的，具体做法现在还没搞清楚。以后再补。。。
后补，搞明白了：主要是阻挡向右走的次数（最后一步都转化为向右走） 然后二分枚举放石子的位置模拟一遍此位置是不是可以即可
1 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 const int MAX= 1e6+10;
6 char str[MAX];
7 int check(int x,int n)
8 {
9 int step=0; int mstep=0;
10 for(int i=0;i<n;i++)
11 {
12 if(str[i]=='R'&&step+1!=x) step++;
13 else if(str[i]=='L') step--;
14 if(i<n-1)
15 mstep=min(mstep,step);
16 }
17 return step<mstep;
18
19 }
20 int main()
21 {
22 scanf("%s",str);
23 int n=strlen(str);
24 if(str[n-1]=='R') for(int i=0;i<n;i++)
25 if(str[i]=='R') str[i]='L';
26 else str[i]='R';
27 if(check(MAX,n)) printf("1 ");
28 else
29 {
30 int L=1,R=n; int ans=0;
31 while(L<=R)
32 {
33 int mid=(L+R)>>1;
34 if(check(mid,n)) ans=mid,L=mid+1;
35 else R=mid-1;
36 }
37 printf("%d ",ans);
38 }
39 return 0;
40 }