比赛地址【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[], vis[];
int N;
int main ()
{
int sum = ;
scanf("%d", &N);
for(int i = ; i <= N; i++)
{
scanf("%d", &a[i]);
sum += a[i];
}
sum /= N / ;
for(int i = ; i <= N; i++)
{
if(vis[i]) continue;
vis[i] = ;
int t = sum - a[i];
for(int j = i + ; j <= N; j++)
{
if(vis[j]) continue;
if(a[j] == t)
{
printf("%d %d\n", i, j);
vis[j] = ;
break;
}
}
}
return ;
}
法二：
#include<bits/stdc++.h>
using namespace std;
struct node
{
int nu, id;
bool operator <(const node x)const
{
return nu < x.nu;
}
} A[];
int N;
int main ()
{
scanf("%d", &N);
for(int i = ; i <= N; i++)
{
scanf("%d", &A[i].nu);
A[i].id = i;
}
sort(A + , A + N + );
int s = , t = N;
while(s <= t)
{
printf("%d %d\n", A[s].id, A[t].id);
s++, t--;
}
return ;
}
题目二：【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 = ;
char S[MAXN];
int T, N;
int main ()
{
scanf("%d", &T);
getchar();
while(T--)
{
gets(S + );
N = strlen(S + );
if(S[] == ' ')//第一种情况
{
printf("Yes\n");
continue;
}
stack<char>st;
for(int i = ; 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\n");
else printf("No\n");
}
return ;
}
题目C:【http://codeforces.com/problemset/problem/382/C】/模拟
题意：给出一列数，使得加入一个数，使他是等差数列。从小到大输出可能的数，如果没有输出0，无限多个-1;
错了好多发。思维;
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + ;
map<int, int>mp;
int a[MAXN], N;
int main ()
{
scanf("%d", &N);
for(int i = ; i <= N; i++)
scanf("%d", &a[i]);
sort(a + , a + N + );
if(N == ) printf("-1\n");
else if(N == )
{
if(a[] == a[]) printf("1\n%d\n", a[]);
else
{
int t = a[] + a[];
if(t % )
printf("2\n%d %d\n", * a[] - a[], * a[] - a[]);
else
printf("3\n%d %d %d\n", * a[] - a[], t / , * a[] - a[]);
}
}
else
{
int t1 = -, t2 = -, p1, p2, nu = ;
for(int i = ; i < N; i++)
{
int t = a[i + ] - a[i];
if(mp.count(t)) {mp[t]++;continue;}
nu++;
mp[t] = ;
if(nu == )
t1 = t, p1 = i;
else if(nu == )
t2 = t, p2 = i;
else break;
}
if(nu == )
{
if(t1 == ) printf("1\n%d\n", a[]);
else printf("2\n%d %d\n", a[] - t1, a[N] + t1);
}
else if(nu == )
{
if(t1 > t2)
{
int t = a[p1] + a[p1 + ];
if(t1 != * t2||mp[t1]!=) printf("0\n");
else printf("1\n%d\n", t / );
}
else
{
int t = a[p2] + a[p2 + ];
if(t2 != * t1||mp[t2]!=) printf("0\n");
else printf("1\n%d\n", t / );
}
}
else printf("0\n");
}
return ;
}
题目四：【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 + ;
const int mod = ;
int N;
LL fast_mod(int x)
{
LL bas = , ans = ;
while(x)
{
if(x & )
ans = ((ans % mod) * (bas % mod)) % mod;
bas = ((bas % mod) * (bas % mod)) % mod;
x >>= ;
}
return ans % mod;
}
int main ()
{
int T, ic = ;
scanf("%d", &T);
while(T--)
{
scanf("%d", &N);
N <<= ;
LL ans = (fast_mod(N - ) - + mod) % mod;
for(int i = ; i <= N >> ; i++)
{
LL t = N / i - ;
LL x = N - i - t;
ans = (ans + (fast_mod(x) * ((fast_mod(t) - + mod) % mod)) % mod) % mod;
}
printf("Case %d: %lld\n", ++ic, ans); }
return ;
}
题目五：【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 = ;
int dp[MAXN][MAXN];
int a[MAXN];
int N;
int main ()
{
scanf("%d",&N);
for(int i=;i<=N;i++)
{
scanf("%d",&a[i]);
dp[i][i]=;
}
for(int l=;l<=N;l++)
{
for(int i=;i<=N-l+;i++)
{
int j=i+l-;
dp[i][j]=INF;
if(a[i]==a[j])
{
if(i+==j)
dp[i][j]=dp[i+][j-]+;
else
dp[i][j]=dp[i+][j-];
}
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);
}
}
printf("%d\n",dp[][N]);
return ;
}