A. Iterated Difference
A题是水题，刚开始一直没看懂，英语拙计。就是给你一个数组，判断数组中的每一个数字是否相同。如果不同则按照
a[k] = a[k]-a[k+1]来更换数组，当达到目标状态时经过了几次变换。如果变换次数超过1000次还没有达到状态时，就
输出“not attained”。就是模拟着写就成：
代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int QuickMod(int a,int b,int n)
{
int r = 1;
while(b)
{
if(b&1)
r = (r*a)%n;
a = (a*a)%n;
b >>= 1;
}
return r;
}
#define maxn 50
int n;
int ans;
int num[maxn];
int solve()
{
while(1)
{
int flag = 0;
if(ans > 1000)
return -1;
for(int i = 0; i < n-1; ++i)
{
if(num[i]!=num[i+1])
{
flag = 1;
break;
}
}
if(flag == 1)
{
ans++;
int tp = num[0];
for(int i = 0; i < n-1; ++i)
num[i] = abs(num[i] - num[i+1]);
num[n-1] = abs(num[n-1] - tp);
}
else
break;
}
return ans;
}
int main()
{
int cnt = 0;
while(scanf("%d", &n) && n)
{
mem(num, 0);
cnt++;
for(int i = 0; i < n; ++i)
scanf("%d", &num[i]);
ans = 0;
int app = solve();
printf("Case %d: ", cnt);
if(app == -1)
printf("not attained\n");
else
printf("%d iterations\n", app);
}
return 0;
}
C. Stock Prices
C题也是签到，排序的问题。只不过对于求前k1小的时候需要对天数按照升序排列，求前k2大的时候反之。比赛中
judge error了，在外面交的。就是排序即可：
代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
#define maxn 1000001
struct node
{
int day;
int price;
} num[maxn];
bool cmp(node a, node b)
{
if(a.price == b.price)
return a.day < b.day;
return a.price < b.price;
}
bool cmp1(node a, node b)
{
if(a.price == b.price)
return a.day > b.day;
return a.price > b.price;
}
int baocun1[maxn];
int baocun2[maxn];
bool cmpp(int a, int b)
{
return a > b;
}
int main()
{
int n, k1, k2;
int cnt = 0;
while(scanf("%d%d%d", &n, &k1, &k2))
{
if(n == 0 && k1 == 0 && k2 == 0)
break;
cnt++;
memset(num, 0, sizeof(num));
for(int i = 0; i < n; ++i)
{
scanf("%d", &num[i].price);
num[i].day = i+1;
}
printf("Case %d\n", cnt);
memset(baocun1, 0, sizeof(baocun1));
memset(baocun2, 0, sizeof(baocun2));
int con1 = 0, con2 = 0;
sort(num, num+n, cmp);
for(int i = 0; i < k1; ++i)
baocun1[con1++] = num[i].day;
sort(num, num+n, cmp1);
for(int i = 0; i < k2 ; ++i)
baocun2[con2++] = num[i].day;
sort(baocun1, baocun1+con1);
sort(baocun2, baocun2+con2, cmpp);
for(int i = 0; i < con1; ++i)
{
if(i == 0)
printf("%d", baocun1[i]);
else
printf(" %d", baocun1[i]);
}
printf("\n");
for(int i = 0; i < con2; ++i)
{
if(i == 0)
printf("%d", baocun2[i]);
else
printf(" %d", baocun2[i]);
}
printf("\n");
}
return 0;
}
E. Pills
E题：卡特兰数（卡特兰数百科）。就是意思是说，对于N棵药，每次吃药时随机从药瓶中拿出一颗，如果拿出的是整
颗那么就掰一半，把剩余的一半扔回药瓶。问你对于这样的吃药方式，有多少种方法可以吃完药。神奇的数论...
代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
long long C[63][63];
long long A[63];
void init()
{
C[0][0] = 1;
C[1][1] = 1;
for(int i = 2; i <= 62; ++i)
{
C[i][0] = 1;
C[i][i] = 1;
C[i][1] = i;
for(int j = 2; j <= i; ++j)
C[i][j] = C[i-1][j] + C[i-1][j-1];
}
}
int main()
{
init();
long long n;
while(scanf("%lld",&n))
{
if(n==0)
break;
//cout << C[2*n][n] << endl;
printf("%lld\n", C[2*n][n]/(n+1));
}
return 0;
}
G. User Names
刚刚做了快2个多小时了，ＷＡＷＡＷＡ，选择从后面找的方法后就A了。我觉得就是ｎｅｍｅ的格式的关系了。从后
面找的话找到第一个空格的话那么肯定找到的是ｌａｓｒ ｎａｍｅ但是要是从前面开始找的话就不一定了。WA和Ａ
C代码就这里不一样．．
代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
char str[100];
string ans;
int n, m;
map<string, int> Q;
int main()
{
int cas = 0;
while(scanf("%d%d", &n, &m))
{
cas++;
if(!n && !m)
break;
getchar();
Q.clear();
printf("Case %d\n", cas);
int cnt = 0;
mem(str, 0);
while(n--)
{
gets(str);
ans = "";
int len = strlen(str);
//int st1 = 0, st2 = 0;
for(int lp = 0; lp < len; ++lp)
{
if(str[lp] >= 'A' && str[lp] <= 'Z')
{
ans+= (str[lp] + 32);
break;
}
else if(str[lp] >= 'a' && str[lp] <= 'z')
{
ans += str[lp];
break;
}
}
int ii;
for(ii = len-1; ii >= 0; --ii)
{
if(str[ii] == ' ')
break;
}
for(int i = ii+1; i < len; ++i)
{
if(str[i] >= 'A' && str[i] <= 'Z')
{
ans+= (str[i] + 32);
}
else if(str[i] >= 'a' && str[i] <= 'z')
{
ans += str[i];
}
}
// int kong = 0;
// for(st1 = 0; st1 < len; ++st1)
// {
// if(str[st1] == ' ')
// {
// break;
// }
// }
// int flag = 0;
// for(st2 = st1+1; st2 < len; ++st2)
// {
// if(str[st2] == ' ')
// {
// flag = 1;
// break;
// }
// else if(str[st2] >= 'A' && str[st2] <= 'Z')
// {
// ans += (str[st2] + 32);
// }
// else if(str[st2] >= 'a' && str[st2] <= 'z')
// {
// ans += str[st2];
// }
//
// }
// if(flag == 1)
// {
// ans = "";
// for(int lp = 0; lp < len; ++lp)
// {
// if(str[lp] >= 'A' && str[lp] <= 'Z')
// {
// ans+= (str[lp] + 32);
// break;
// }
// else if(str[lp] >= 'a' && str[lp] <= 'z')
// {
// ans += str[lp];
// break;
// }
// }
// for(int k = st2+1; k < len; ++k)
// {
// if(str[k] >= 'A' && str[k] <= 'Z')
// {
// ans += (str[k] + 32);
// }
// else if(str[k] >= 'a' && str[k] <= 'z')
// {
// ans += str[k];
// }
// }
// }
int add = ans.length();
if(Q[ans] == 0)
{
Q[ans] ++;
if(add > m)
{
for(int i = 0; i < m; ++i)
printf("%c", ans[i]);
printf("\n");
}
else
cout << ans << endl;
}
else
{
Q[ans]++;
cnt = Q[ans] - 1;
if(cnt <= 9)
{
if(add <= m-1)
{
ans += (cnt + '0');
cout << ans << endl;
}
else
{
for(int i = 0; i < m-1; ++i)
printf("%c", ans[i]);
cout << cnt << endl;
}
}
else
{
if(add <= m-2)
{
int shi = cnt/10;
int ge = cnt%10;
ans += (shi + '0');
ans += (ge + '0');
cout << ans << endl;
}
else if(add == m-1)
{
int shi = cnt/10;
int ge = cnt%10;
ans[m-2] = (shi + '0');
ans += (ge + '0');
cout << ans << endl;
}
else
{
for(int i = 0; i < m-2; ++i)
printf("%c", ans[i]);
cout << cnt << endl;
}
}
}
}
}
return 0;
}
/*
2 6
Jenny Ax
Christos H Papadimitriou
11 8
Jean-Marie d'Arboux
Jean-Marie A d'Arboux
Jean-Marie B d'Arboux
Jean-Marie C d'Arboux
Jean-Marie D d'Arboux
Jean-Marie D d'Arboux
Jean-Marie F d'Arboux
Jean-Marie G d'Arboux
Jean-Marie H d'Arboux
Jean-Marie I d'Arboux
Jean-Marie J d'Arboux
11 9
Jean-Marie d'Arboux
Jean-Marie A d'Arboux
Jean-Marie B d'Arboux
Jean-Marie C d'Arboux
Jean-Marie D d'Arboux
Jean-Marie D d'Arboux
Jean-Marie F d'Arboux
Jean-Marie G d'Arboux
Jean-Marie H d'Arboux
Jean-Marie I d'Arboux
Jean-Marie J d'Arboux
*/
H. Citizenship Application
迷之WA，看了数据都不懂了。。。。
代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node
{
int year;
int mon;
int day;
} num[210];
int judge(int m)
{
if(m % 400 == 0)
return true;
else if(m % 4 == 0)
return true;
return false;
}
int P[15] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30,31};
int con;
void init()
{
for(int i = 1; i <= 12; ++i)
con += P[i];
}
int cal(int year, int mon, int day)
{
int sum = 0;
for(int i = 1980; i <= year-1; ++i)
{
if(!judge(i))
sum += con;
else
sum += (con+1);
}
for(int i = 1; i <= mon-1; ++i)
{
sum += P[i];
if(i == 2 && judge(year))
sum ++;
}
sum += day;
return sum;
}
void solve(int &year, int &mon, int &day, int &sum)
{
while(sum >= 0)
{
int flag = 0;
if(mon <= 11)
{
if(judge(year) && mon == 2)
sum -= (P[mon] + 1);
else sum -= P[mon];
mon++;
if(sum < 0)
break;
}
else
{
year++;
mon = 1;
sum -= 31;
if(sum < 0)
break;
}
}
if(mon == 1)
{
mon = 12;
year--;
sum += 31;
}
else
{
mon --;
sum += (P[mon]);
}
int tp;
tp = sum - (P[mon] - day);
if(tp > 0)
{
mon++;
day = tp;
}
else
{
day += sum;
}
}
int main()
{
int n;
while(scanf("%d", &num[0].mon) != EOF)
{
con = 0;
init();
scanf("/%d/%d", &num[0].day, &num[0].year);
scanf("%d/%d/%d", &num[1].mon, &num[1].day, &num[1].year);
int sum = 0;
int tmp = cal(num[1].year, num[1].mon, num[1].day);
int tmp1 = cal(num[0].year, num[0].mon, num[0].day);
scanf("%d", &n);
int SUM = 0;
int span = 0;
for(int i = 2; i < 2*n+2; i += 2)
{
int MAX = tmp;
int MIN = tmp;
scanf("%d/%d/%d", &num[i].mon, &num[i].day, &num[i].year);
scanf("%d/%d/%d", &num[i+1].mon, &num[i+1].day, &num[i+1].year);
int p1 = cal( num[i].year,num[i].mon, num[i].day);
int p2 = cal(num[i+1].year,num[i+1].mon, num[i+1].day);
if(p2 <= tmp) {
span += p2 - p1;
}
else
{
MIN = min(tmp,p1);
span += tmp - MIN;
MAX = max(tmp, p1);
SUM += (p2 - MAX);
}
}
//cout << "SUM:-> " << SUM << endl;
sum = ( tmp - tmp1 - span ) / 2;
sum = 1095 - sum + SUM + n;
solve(num[1].year, num[1].mon, num[1].day, sum);
//cout << "-----------" << endl;
printf("%d/%d/%d\n", num[1].mon, num[1].day, num[1].year);
//cout << "-------------" <<endl;
}
return 0;
}
迷．．．．．