比赛地址【https://vjudge.net/contest/147011#problem/A】、960626
题目一：【http://codeforces.com/problemset/problem/701/A】、水题
题意：给出N张纸牌，N为偶数，每张纸牌上有数值，把这N张纸牌分给（N/2）个人，每个人分到两张纸牌，并且数值相同。一定存在解。
法一：
#include<bits/stdc++.h> using namespace std; int a[200], vis[200]; int N; int main () { int sum = 0; scanf("%d", &N); for(int i = 1; i <= N; i++) { scanf("%d", &a[i]); sum += a[i]; } sum /= N / 2; for(int i = 1; i <= N; i++) { if(vis[i]) continue; vis[i] = 1; int t = sum - a[i]; for(int j = i + 1; j <= N; j++) { if(vis[j]) continue; if(a[j] == t) { printf("%d %d ", i, j); vis[j] = 1; break; } } } return 0; }
法二：
#include<bits/stdc++.h> using namespace std; struct node { int nu, id; bool operator <(const node x)const { return nu < x.nu; } } A[150]; int N; int main () { scanf("%d", &N); for(int i = 1; i <= N; i++) { scanf("%d", &A[i].nu); A[i].id = i; } sort(A + 1, A + N + 1); int s = 1, t = N; while(s <= t) { printf("%d %d ", A[s].id, A[t].id); s++, t--; } return 0; }
题目二：【https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=614】
题意：
You are given a string consisting of parentheses () and []. A string of this type is said to be correct:
(a) if it is the empty string
(b) if A and B are correct, AB is correct,
(c) if A is correct, (A) and [A] is correct.
Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.
题解：虽然长度最长只有128，但是是多组输入，用区间DP会TLE。简单stack的应用。
#include<stack> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int INF = 1e6; const int MAXN = 150; char S[MAXN]; int T, N; int main () { scanf("%d", &T); getchar(); while(T--) { gets(S + 1); N = strlen(S + 1); if(S[1] == ' ')//第一种情况 { printf("Yes "); continue; } stack<char>st; for(int i = 1; i <= N; i++) { if(!st.empty() && ((st.top() == '(' && S[i] == ')') || (st.top() == '[' && S[i] == ']'))) st.pop();//匹配 else st.push(S[i]); } if(st.empty()) printf("Yes "); else printf("No "); } return 0; }
题目C:【http://codeforces.com/problemset/problem/382/C】/模拟
题意：给出一列数，使得加入一个数，使他是等差数列。从小到大输出可能的数，如果没有输出0，无限多个-1;
错了好多发。思维;
#include<bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 15; map<int, int>mp; int a[MAXN], N; int main () { scanf("%d", &N); for(int i = 1; i <= N; i++) scanf("%d", &a[i]); sort(a + 1, a + N + 1); if(N == 1) printf("-1 "); else if(N == 2) { if(a[1] == a[2]) printf("1 %d ", a[1]); else { int t = a[1] + a[2]; if(t % 2) printf("2 %d %d ", 2 * a[1] - a[2], 2 * a[2] - a[1]); else printf("3 %d %d %d ", 2 * a[1] - a[2], t / 2, 2 * a[2] - a[1]); } } else { int t1 = -1, t2 = -1, p1, p2, nu = 0; for(int i = 1; i < N; i++) { int t = a[i + 1] - a[i]; if(mp.count(t)) {mp[t]++;continue;} nu++; mp[t] = 1; if(nu == 1) t1 = t, p1 = i; else if(nu == 2) t2 = t, p2 = i; else break; } if(nu == 1) { if(t1 == 0) printf("1 %d ", a[1]); else printf("2 %d %d ", a[1] - t1, a[N] + t1); } else if(nu == 2) { if(t1 > t2) { int t = a[p1] + a[p1 + 1]; if(t1 != 2 * t2||mp[t1]!=1) printf("0 "); else printf("1 %d ", t / 2); } else { int t = a[p2] + a[p2 + 1]; if(t2 != 2 * t1||mp[t2]!=1) printf("0 "); else printf("1 %d ", t / 2); } } else printf("0 "); } return 0; }
题目四：【http://www.spoj.com/problems/INTSUB/en/】快速幂
题意：输入一个数n,有区间【1，2n】找出一个区间，区间中存在数a、b，使得a为区间中最小的数，b为a的整倍数数。
题解：枚举最小的数a,利用组合数公式求出所有的可能的情况，中间用快速幂处理。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 1e5 + 15; const int mod = 1000000007; int N; LL fast_mod(int x) { LL bas = 2, ans = 1; while(x) { if(x & 1) ans = ((ans % mod) * (bas % mod)) % mod; bas = ((bas % mod) * (bas % mod)) % mod; x >>= 1; } return ans % mod; } int main () { int T, ic = 0; scanf("%d", &T); while(T--) { scanf("%d", &N); N <<= 1; LL ans = (fast_mod(N - 1) - 1 + mod) % mod; for(int i = 2; i <= N >> 1; i++) { LL t = N / i - 1; LL x = N - i - t; ans = (ans + (fast_mod(x) * ((fast_mod(t) - 1 + mod) % mod)) % mod) % mod; } printf("Case %d: %lld ", ++ic, ans); } return 0; }
题目五：【http://codeforces.com/problemset/problem/607/B】
题意：给出n个数，每次删除一个回文串，求最少的删除次数。
题解：区间DP,dp[l][r],表示区间[l,r]中最少的回文串。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int INF=1e9; const int MAXN = 550; int dp[MAXN][MAXN]; int a[MAXN]; int N; int main () { scanf("%d",&N); for(int i=1;i<=N;i++) { scanf("%d",&a[i]); dp[i][i]=1; } for(int l=2;l<=N;l++) { for(int i=1;i<=N-l+1;i++) { int j=i+l-1; dp[i][j]=INF; if(a[i]==a[j]) { if(i+1==j) dp[i][j]=dp[i+1][j-1]+1; else dp[i][j]=dp[i+1][j-1]; } for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); } } printf("%d ",dp[1][N]); return 0; }