A：博弈問題，一個矩形中，放入半徑等於r的圓，誰不能放，就輸了。
一開始比較茫然，仔細想一下發現有對稱性質，一開始在中心放入一個圓，便將矩形分為對稱區域，對手放入一個圓，則自己可以在對稱的區域相同的位置放入圓。
[cpp]
#include<iostream>
#include<cstring>
#include<queue>
#include<string>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>
#define N 105
using namespace std;
int main(){
int a,b,r;
while(scanf("%d%d%d",&a,&b,&r)!=EOF){
if(2*r>a||2*r>b)
printf("Second\n");
else
printf("First\n");
}
return 0;
}
B：取極限問題，比較簡單，想清楚所有的情況就OK了
[cpp]
#include<iostream>
#include<cstring>
#include<queue>
#include<string>
#include<cstdio>
#include<algorithm>
#define N 105
using namespace std;
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int main(){
int n,m;
int a[105],b[105];
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=0;i<=n;i++)
scanf("%d",&a[i]);
for(int j=0;j<=m;j++)
scanf("%d",&b[j]);
if(n==m){
if(a[0]*b[0]<0)
printf("-");
printf("%d/%d\n",abs(a[0])/gcd(abs(a[0]),abs(b[0])),abs(b[0])/gcd(abs(a[0]),abs(b[0])));
}
else if(n>m){
if(a[0]*b[0]<0)
printf("-");
printf("Infinity\n");
}
else
printf("0/1\n");
}
return 0;
}
C：選出字典序最大的子序列，維護一個單調棧就OK了
[cpp]
#include<iostream>
#include<cstring>
#include<queue>
#include<string>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>
#define N 105
using namespace std;
char str[200005];
stack<char>s,ans;
int main(){
while(scanf("%s",str)!=EOF){
while(!s.empty())
s.pop();
while(!ans.empty())
ans.pop();
int len=strlen(str);
for(int i=0;i<len;i++){
if(s.empty())
s.push(str[i]);
else{
if(str[i]<=s.top())
s.push(str[i]);
else{
while(1){
if(s.empty())
break;
if(str[i]>s.top())
s.pop();
else
break;
}
s.push(str[i]);
}
}
}
while(!s.empty()){
ans.push(s.top());
s.pop();
}
while(!ans.empty()){
printf("%c",ans.top());
ans.pop();
}
printf("\n");
}
return 0;
}
D：一個無限大的地圖，問是否能無限走下去。
對於每一個位置，如果可以從多個位置到達，則說明進入了循環，便將是可以無限移動的。
[cpp]
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<vector>
#define eps 1e-10
#define LL long long
#define LD long double
#define pi acos(-1.0)
using namespace std;
struct Node{
int x,y;
}s,u,v,tt;
int n,m;
int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool flag[1505][1505];
int vis[1505][1505][2];
char str[1505][1505];
bool bfs(){
queue<Node>que;
que.push(s);
memset(flag,false,sizeof(flag));
while(!que.empty()){
u=que.front(); www.2cto.com
que.pop();
for(int i=0;i<4;i++){
v=u;
v.x+=way[i][0];
v.y+=way[i][1];
tt.x=((v.x%n)+n)%n;
tt.y=((v.y%m)+m)%m;
if(str[tt.x][tt.y]=='#')
continue;
if(flag[tt.x][tt.y]){
if(v.x!=vis[tt.x][tt.y][0]||v.y!=vis[tt.x][tt.y][1])
return true;
}
else{
flag[tt.x][tt.y]=true;
vis[tt.x][tt.y][0]=v.x;
vis[tt.x][tt.y][1]=v.y;
que.push(v);
}
}
}
return false;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=0;i<n;i++){
scanf("%s",str[i]);
for(int j=0;j<m;j++)
if(str[i][j]=='S'){
s.x=i;
s.y=j;
}
}
printf("%s\n",bfs()?"YES":"NO");
}
return 0;
}
