比赛链接： http://acm.uestc.edu.cn/contest.php?cid=230
A.Police And The Thief ---UESTC 1913
简单博弈，先假设在警察先走的情况下分析，小偷先走的结果在其基础上取反面即可。我是这样做的，随便假设小偷在一个点，在这个点的四周都是必败态（警察抓不到），然后一步可以到达必败态的点都是必胜态，一次推向远处，容易发现规律： 当abs(xp-xt)%2==abs(yp-yt)%2时都是必败态，否则是必败态，这是结果已经得出。
两个特殊情况： 1.开始时两人在同一点，算YES。
2.格子为n*1或1*m形式，必然可以抓到，算YES。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <time.h>
#include <queue>
#include <cctype>
#include <numeric>
#include <cstdlib>
#include <iomanip>
#include <sstream>
#define mod 1000000007
#define INT 2147483647
#define pi acos(-1.0)
#define eps 1e-3
#define lll __int64
#define ll long long
using namespace std;
#define N 200005 int main()
{
int t,i;
int n,m;
int xp,yp,xt,yt;
int flag;
char ss[];
scanf("%d",&t);
while(t--)
{
flag = ;
scanf("%d%d",&n,&m);
scanf("%d%d%d%d",&xp,&yp,&xt,&yt);
scanf("%s",ss);
if((n == || m == )||(xp == xt && yp == yt))
{
cout<<"YES\n";
continue;
}
int ka = abs(yp-yt);
int kb = abs(xp-xt);
if(ka% == kb%)
{
flag = ;
} if(ss[] == 'p')
{
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
else
{
if(flag)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
}
return ;
}
B.Similar strings ---UESTC 1916
我的思路如下：从第一个字符串（后文称a）中第一个字符扫起，遇见一个字母（如'A'），如果没有标记，则标记为第二个字符串（后文称b）的该位字母，然后在循环里面扫一遍a，如果有等于这个字母的，而b对应的不相等，或者，不等于这个字母而b对应的又相等了，则tag = 0，说明不是，否则就是。这里最多26个字母，虽然是二重循环，但是不会超时。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <time.h>
#include <queue>
#include <cctype>
#include <numeric>
#include <cstdlib>
#include <iomanip>
#include <sstream>
#define mod 1000000007
#define INT 2147483647
#define pi acos(-1.0)
#define eps 1e-3
#define lll __int64
#define ll long long
using namespace std;
#define N 200005 char flag[]; string tostring(char a)
{
string tmp = "";
tmp +=a;
return tmp;
} int main()
{
string aa,bb;
int t,i;
scanf("%d",&t);
while(t--)
{
memset(flag,,sizeof(flag));
cin>>aa;
cin>>bb;
int j;
if(aa.length()!=bb.length())
{
cout<<"NO"<<endl;
continue;
}
int tag = ;
for(i=;i<aa.length();i++)
{
if(!flag[aa[i]-'A'])
{
flag[aa[i]-'A'] = bb[i];
for(j = i+;j<aa.length();j++)
{
if(aa[i] == aa[j])
{
if(bb[i] != bb[j])
{
tag = ;
break;
}
}
else
{
if(bb[i] == bb[j])
{
tag = ;
break;
}
}
}
}
} if(tag)
cout<<"YES\n";
else
cout<<"NO"<<endl;
}
return ;
}
C.The Game of Little P ---UESTC 1915
简单推公式题，公式很简单： ans = m*(m+1)*(2*m+1)/6 * n/(m+1) + modi*(modi+1)*(2*modi+1)/6 . 【modi = n%(m+1)】 难就难在计算出这个结果，又因为有取模的性质：(A * B) mod C = ((A mod C) * (B mod C)) mod C， 但是除法并不满足，所以要看m*(m+1)*(2*m+1)这个里面有没有可以被6整除的一个或两个数，先把6除掉，然后再用取模的性质解决。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <time.h>
#include <queue>
#include <cctype>
#include <numeric>
#include <cstdlib>
#include <iomanip>
#include <sstream>
#define mod 1000000007
#define INT 2147483647
#define pi acos(-1.0)
#define eps 1e-3
#define lll __int64
#define ll long long
using namespace std;
#define Mod 1000000007LL long long calc(long long m)
{
long long ka,res;
long long a = m*(m+);
long long b = *m+;
long long c = m*(*m+);
long long d = (m+)*(*m+);
if(m%==) //
{
ka = m/;
ka = ((ka%Mod)*((m+)%Mod))%Mod;
res = ((ka%Mod)*(b%Mod))%Mod;
}
else if((m+)%==) //
{
ka = (m+)/;
ka%=Mod;
res = ((m%Mod)*ka)%Mod;
res = (res*(b%Mod))%Mod;
}
else if(b%==) //
{
b/=;
res = ((a%Mod)*(b%Mod))%Mod;
}
else if(a%==) //deux
{
a/=;
res = ((a%Mod)*(b%Mod))%Mod;
}
else if(c%==)
{
ka = c/;
res = ((ka%Mod)*((m+)%Mod))%Mod;
}
else if(d%==)
{
ka = d/;
res = ((ka%Mod)*(m%Mod))%Mod;
}
return res%Mod;
} int main()
{
long long int n,m;
int modi,i;
int t;
scanf("%d",&t);
while(t--)
{
long long res;
scanf("%lld%lld",&n,&m);
modi = n%(m+);
res = calc(m);
res = (res*(n/(m+)))%Mod;
long long cas = calc(modi);
long long ans = (res+cas)%Mod;
cout<<ans<<endl;
}
return ;
}
D.Trees ----UESTC 1918
这题开始没想通，后来看了别人的解法才知道原来是多么弱的题，用贪心就行了，因为最少也应该满足1 2 3...3 2 1形式，先做一个假设数组就是1 2 3...3 2 1，然后再使输入的tree数组减去assume数组，得出差异，取差出现最多的一些数让他们不动，其余的都得动，当然，如果差小于0，那更是必须得动，此时动的树的数目一定是最小的。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <time.h>
#include <queue>
#include <cctype>
#include <numeric>
#include <cstdlib>
#include <iomanip>
#include <sstream>
#define Mod 1000000007
#define INT 2147483647
#define pi acos(-1.0)
#define eps 1e-3
#define lll __int64
#define ll long long
using namespace std; int tree[];
int assume[];
int dif[];
int flag[]; int main()
{
int n,i,j;
int t;
scanf("%d",&t);
while(t--)
{
memset(flag,,sizeof(flag));
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d",&tree[i]);
}
int mid = (n+)/;
for(i=;i<=mid;i++)
{
assume[i] = i;
}
for(i=mid+;i<=n;i++)
{
assume[i] = assume[n-i+];
}
int maxdif = -;
int diftag;
for(i=;i<=n;i++)
{
dif[i] = tree[i]-assume[i];
if(dif[i]>=)
{
flag[dif[i]]++;
if(flag[dif[i]]>maxdif)
{
maxdif = flag[dif[i]];
diftag = dif[i];
}
}
}
int cnt = ;
for(i=;i<=n;i++)
{
if(dif[i]!=diftag)
{
cnt++;
}
}
cout<<cnt<<endl;
}
return ;
}
其余的还没做出来，等我后面更新。。有错误欢迎指正。