T1：FUNGHI（1s,32M,50pts）得分：50
题意：给你8个数组成一个环，要你求出其中连续的4个数，让它们的和最大
题解：暴力求出每一连续4个数之和，比较一下就好
标签：模拟
C++ Code：
#include<cstdio>
using namespace std;
int s[10],ans,maxn;
int main(){
freopen("FUNGHI.in","r",stdin);
freopen("FUNGHI.out","w",stdout);
for (int i=0;i<8;i++)scanf("%d",&s[i]);
for (int i=0;i<8;i++){
ans=0;
for (int j=0;j<4;j++)ans+=s[(i+j)%8];
if (ans>maxn)maxn=ans;
}
printf("%d
",maxn);
return 0;
}
T2：ZMIJA（1s,32M,80pts）得分：80
题意：给你一个n*m的矩阵，有一条蛇在左下角（用“Z”表示），有一些苹果（用“J”表示）和空格（用“.”表示）。有两个操作，A：让蛇向它面朝的方向走一步（不可以走出矩阵），B：让蛇向上走一步，并且转向180°（左变右，右变左）。现在它面向右，让你求出最小操作几次使得蛇吃完所有的苹果。
题解：分析每一行，如果((n-i+1)&1)（在从下到上的奇数行，即面向右），为了吃完这一行所有苹果，到这一行时必须到这一行最左边的苹果的左边（或相同）；如果是偶数行，就必须到这一行最右边的苹果的右边（或相同）。满足这就可以保证吃完苹果。为了操作数最少，如果可以的话就刚好到达最左或右的苹果（即在吃完苹果的前提下不多走路）。注意，如果上面几行是空行，就不必上去，不然操作数会多
标签：模拟，贪心
C++ Code：
#include<cstdio>
using namespace std;
int n,m,ans,tmp,x=1,tmp6;
char ch[1010];
bool s[1010][1010],pd,yes=1;
int main(){
freopen("ZMIJA.in","r",stdin);
freopen("ZMIJA.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%s",ch);
pd=1;
for (int j=1;j<=m;j++){
s[i][j]=ch[j-1]=='J';
if (s[i][j])pd=0;
}
if (pd&&yes)tmp6++;
else yes=0;
}
for (int i=n;i;i--){
if ((n-i+1)&1){
tmp=x;
for (int j=x+1;j<=m;j++)if (s[i][j])tmp=j;
ans+=tmp-x;
x=tmp;
}else{
tmp=x;
for (int j=x-1;j;j--)if (s[i][j])tmp=j;
ans+=x-tmp;
x=tmp;
}
if (i==1)break;
if ((n-i)&1){
for (int j=1;j<x;j++)if (s[i-1][j]){
ans+=x-j;
x=j;
break;
}
}else{
for (int j=m;j>x;j--)if (s[i-1][j]){
ans+=j-x;
x=j;
break;
}
}
ans++;
}
if (yes){
puts("0");
return 0;
}
printf("%d
",ans-tmp6);
return 0;
}
T3：TRAKTOR（2s,32M,100pts）得分：100
题意：平面上有n个整点，问最小的i满足前i个点中已经出现k点共线（这里的线只可以平行与坐标轴或者成45°），无解输出-1
题解：维护4个数组，分别记录这一行、这一列、左上到右下的对角线、左下到右上的对角线，每读进一个蘑菇的坐标就维护一下这些数组，看最早什么时候值大于等于k
标签：模拟，数论
C++ Code：
#include<cstdio>
using namespace std;
int n,k;
int h[100010],l[100010],x[200020],y[200020];
int main(){
freopen("TRAKTOR.in","r",stdin);
freopen("TRAKTOR.out","w",stdout);
scanf("%d%d",&n,&k);
if (n<1){
puts("-1");
return 0;
}
if (k==0){
puts("0");
return 0;
}
for (int i=1;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
h[a]++;
l[b]++;
if ((h[a]>=k)||(l[b]>=k)){
printf("%d
",i);
return 0;
}
x[a+b]++;
y[a-b+100010]++;
if ((x[a+b]>=k)||(y[a-b+100010]>=k)){
printf("%d
",i);
return 0;
}
}
puts("-1");
return 0;
}
T4：ZGODAN（1s,32M,120pts）得分：120
题意：给你一个数N（N≤10^1000），询问离它最近的美丽数（美丽数定义：这个数中，任意两个相邻的数字奇偶性不同），如果有两个美丽数距离N一样，先输出小的，再输出大的
题解：发现找到第一个奇偶性不同的数，然后把它+1或-1。如果+1，后面的数为0101……或1010……（根据奇偶性决定）；如果-1，后面的数为8989……或9898……（根据奇偶性决定）。然后判断一下这两个和原数差的大小即可。注意，如果+1或-1后不在0~9内就不用判断，因为这样会改变前一个数的奇偶性，差一定比另一个数大
标签：数论，高精度
C++ Code：
#include<cstdio>
#include<cstring>
using namespace std;
char s[1010];
bool pd=0,bb=1,cc=1;
int a[1010],b[1010],c[1010],d[1010],e[1010],len;
void jian(int *a,int *b,int *c){
int tmp=0;
for (int i=len-1;i;i--){
c[i]=a[i]-b[i]-tmp;
if (c[i]<0)c[i]+=10,tmp=1;
else tmp=0;
}
}
int bj(int *a,int *b){
for (int i=0;i<len;i++)if (a[i]!=b[i])if (a[i]<b[i])return 0;else return 1;
return -1;
}
void work(){
jian(a,b,d);
jian(c,a,e);
int tmp=bj(d,e);
// for (int i=0;i<len;i++)printf("%d",b[i]);
// putchar(' ');
// for (int i=0;i<len;i++)printf("%d",c[i]);
// putchar('
');
if (tmp==1){
for (int i=0;i<len;i++)printf("%d",c[i]);
putchar('
');
}else{
if (tmp==0){
for (int i=0;i<len;i++)printf("%d",b[i]);
putchar('
');
}else{
for (int i=0;i<len;i++)printf("%d",b[i]);
putchar(' ');
for (int i=0;i<len;i++)printf("%d",c[i]);
putchar('
');
}
}
return;
}
int main(){
freopen("ZGODAN.in","r",stdin);
freopen("ZGODAN.out","w",stdout);
scanf("%s",s);len=strlen(s);
for (int i=0;i<len;i++)a[i]=s[i]^48;
b[0]=c[0]=a[0];
for (int i=1;i<len;i++){
if (pd){
if (bb){
if (b[i-1]&1)b[i]=8;
else b[i]=9;
}
if (cc){
if (c[i-1]&1)c[i]=0;
else c[i]=1;
}
}
if (!pd){
b[i]=c[i]=a[i];
if ((a[i]&1)==(a[i-1]&1)){
pd=1;
b[i]=a[i]-1;
c[i]=a[i]+1;
if (b[i]==-1)bb=0;
if (c[i]==10)cc=0;
}
}
}
if (!bb){
for (int i=0;i<len;i++)printf("%d",c[i]);
putchar('
');
return 0;
}
if (!cc){
for (int i=0;i<len;i++)printf("%d",b[i]);
putchar('
');
return 0;
}
work();
return 0;
}
T5：JABUKE（2s,128M,140pts）得分81
题意：给你一个n*m的矩阵，其中有苹果树（用“x”表示）和空地（用“.”表示），有G(1<=G<=10^5)年，每年会掉一个苹果，要你求出每年距该苹果最近的一棵苹果树的距离的平方，每个苹果第二年都会变成苹果树
题解：用p[i][j]存第j列到第i行中最近的苹果树的距离，每发现一棵苹果数就维护一下p数组（就维护这一行的p）。针对每个询问，枚举每一行，看离询问的那一列最近的距离（因为更远的苹果树到该点距离一定比现在的远），更新答案。
标签：数论，贪心
C++ Code：
原：
#include<cstdio>
using namespace std;
int n,m,num,T,minn,ans;
char ch[600];
int s[250100][2];
int main(){
freopen("JABUKE.in","r",stdin);
freopen("JABUKE.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%s",ch);
for (int j=1;j<=m;j++)if (ch[j-1]=='x')s[++num][0]=i,s[num][1]=j;
}
scanf("%d",&T);
while (T--){
int a,b;
scanf("%d%d",&a,&b);
s[++num][0]=a;s[num][1]=b;
minn=2147483647;
for (int i=1;i<num;i++){
ans=0;
int x=s[i][0]-s[num][0],y=s[i][1]-s[num][1];
ans=x*x+y*y;
if (ans<minn)minn=ans;
}
printf("%d
",minn);
}
return 0;
}
正确：
#include<cstdio>
using namespace std;
int n,m,num,T,minn,ans,x,y;
char ch[600];
int s[250100][2],p[510][510];
inline int abs(int a){return a>0?a:-a;}
int main(){
freopen("JABUKE.in","r",stdin);
freopen("JABUKE.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%s",ch);
for (int j=1;j<=m;j++)p[i][j]=600;
for (int j=1;j<=m;j++){
if (ch[j-1]=='x'){
x=i,y=j;
for (int l=1;l<=m;l++){
int a=abs(y-l);
if (p[x][l]>a)p[x][l]=a;
}
}
}
}
scanf("%d",&T);
while (T--){
scanf("%d%d",&x,&y);
minn=2147483647;
for (int i=1;i<=n;i++){
int a=p[i][y],b=i-x;
ans=a*a+b*b;
if (ans<minn)minn=ans;
if (!minn)break;
}
for (int i=1;i<=m;i++){
int a=abs(y-i);
if (p[x][i]>a)p[x][i]=a;
}
printf("%d
",minn);
}
return 0;
}
T6：DIVLJAK（4s,768M,160pts）得分：50
题意：给你多个模式串，要求支持动态增加询问串和询问某个模式串是多少询问串的子串
题解：略
标签：略
C++ Code：
原：
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,s[100010];
string p[100010],tmp;
int main(){
ios::sync_with_stdio(false);
freopen("DIVLJAK.in","r",stdin);
freopen("DIVLJAK.out","w",stdout);
cin >> n;
for (int i=1;i<=n;i++)cin >> p[i];
cin >> m;
while (m--){
int op,o;
cin >> op;
if (op==1){
cin >> tmp;
for (int i=1;i<=n;i++)if (tmp.find(p[i])!=-1)s[i]++;
// printf("Debug:%d
",tmp.find(p[1]));
}else{
cin >> o;
cout << s[o] << endl;
}
}
return 0;
}
正确：
略