#JC0101. Suffix Three
观察题目可知,字符串的倒数第二个字符可以确定语言:
p – Filipino
s – Japanese
d – Korean
int main()
{
int n;
string s;
cin>>n;
for (int i=1;i<=n;i++)
{
s.clear();
cin>>s;
if (s[s.size()-2]=='p') cout<<"FILIPINO\n";
else if (s[s.size()-2]=='s') cout<<"JAPANESE\n";
else if (s[s.size()-2]=='d') cout<<"KOREAN\n";
}
return 0;
}
#JC0102. Dreamoon and Ranking Collection
根据已经得到的名次和接下来要比赛的次数,求能够得到的名次中,从1,2,3……v,v最多为多大。
将已经取得的名次存入桶a中,然后x从1开始遍历,每次将v+1,如果a[x]不存在,则x-1,即消耗一次比赛次数。直到x=0,即用完所有比赛次数。v即为所求。
注意判断当x=0后,a[v+1]是否存在。
int a[1001],t,n,x,v,b;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI t;
while(t--)
{
clear(a);
CI n;CI x;
F(i,1,n)
{
CI b;
a[b]=1;
}
v=0;
while (x>0)
{
v++;
if (!a[v]) x--;
}
while (a[v+1])
v++;
CO v L;
}
return 0;
}
#JC0103. Symmetric Matrix
判断给出的n个2*2矩阵能否填满m*m的矩阵,并且使得m*m矩阵关于左上到右下的对角线对称。
首先m需要是个偶数,不然无法填满。然后n个2*2矩阵中只要有一个可以关于左上到右下的对角线对称,即右上角元素等于左上角元素,则可以得到满足要求的m*m的矩阵。
int t,n,m,x1,x2,f;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI t;
while (t--)
{
CI n>>m;
f=0;
F(i,1,n)
{
CI x1>>x1>>x2;
if (x1==x2) f=1;
CI x2;
}
if (m%2==0&&f) CO "YES" L;
else CO "NO" L;
}
return 0;
}
#JC0104. Happy Birthday, Polycarp!
这道题要求出1-n中有多少个数字是只由一个数构成的。
可以先预处理,求出所有的符合要求的数,然后再计算1-n中有多少符合要求的数。
int t,n,a[1001],x;
int main()
{
string str="";
x=1;
F(i,1,9)
{
str+="1";
int t=stoi(str);
F(j,1,9)
{
a[x]=j*t;
x++;
}
}
a[x]=2000000000;
CI t;
while (t--)
{
CI n;
int ans=0;
while (a[ans+1]<=n)
ans++;
CO ans L;
}
return 0;
}
#JC0105. A New Technique
有一个n*m的矩阵,给出每行的数字但是行之间的顺序是错的,再给出每列的数字,列与列之间的顺序也是错的。需要根据这些信息还原出原来的矩阵。
只需要找到给出的每一行的第一个数字,然后再在给出的列中找到包含这些数字的那一列,就能得到每一行的正确顺序,从而还原矩阵。
int t,n,m,a[1001][1001],b[1001],x;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI t;
while (t--)
{
CI n>>m;
F(i,1,n)
F(j,1,m)
CI a[i][j];
int f=0;
F(i,1,m)
{
F(j,1,n)
{
CI b[j];
if (b[j]==a[1][1]) f=1;
}
if (f)
{
F(j,1,n)
{
F(k,1,n)
if (b[j]==a[k][1])
DBA(a[k],1,m)
}
f=0;
}
}
}
return 0;
}
#JC0106. Reachable Numbers
定义一个操作:+1,然后去除末尾所有的零。给出一个数n,求不断进行这种操作后最多可以得到多少个不同的数字。
先定义一个map,用来存储得到的数字,然后不断的进行上述操作,并将数字存入map中,直到得到的数字已经在map中了。
int n,t=1;
map<int,int> a;
int main()
{
CI n;
a[n]=1;
while (n>0)
{
n++;
while (n%10==0&&n!=0)
n/=10;
if (a[n]) break;
else a[n]=1;
t++;
}
CO t L;
return 0;
}
#JC0107. Collecting Packages
给出一些物品的坐标,从(0,0)处出发,只能向右或向上走,问能否进过所有的物品,并且输出路线。
先将每个物品坐标的x,y相加并从小到大排序,就能得到进过物品的顺序,并且当出现两个物品的x+y和相等,那么必然有其中一个物品是无法进过的。然后模拟移动的过程,在移动中若出现下一个要经过的物品,其x或y坐标中任何一个小于当前的x,y坐标,那么必定无法经过。
int t,n,x,y;
string ans;
struct package{
int x,y,b;
} pack[100001];
bool cmp(package p1,package p2)
{
return p1.b<p2.b;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI t;
while (t--)
{
map<int,int> m;
int f=1;
x=y=0;
ans="";
CI n;
F(i,1,n)
{
CI pack[i].x>>pack[i].y;
pack[i].b=pack[i].x+pack[i].y;
if (m[pack[i].b]) f=0;
m[pack[i].b]=1;
}
if (f)
{
sort(pack+1,pack+n+1,cmp);
F(i,1,n)
{
if (pack[i].x<x||pack[i].y<y)
{
f=0;
break;
}
F(j,x,pack[i].x-1)
ans+="R";
x=pack[i].x;
F(j,y,pack[i].y-1)
ans+="U";
y=pack[i].y;
}
}
if (f) CO "YES" L<<ans L;
else CO "NO" L;
}
return 0;
}
#JC0108. Yet Another Crosses Problem
输入一张由*
,.
构成的图,判断哪个点所在行、列的*总数最多,并计算出还需要补充多少*才能填满所在行、列。
输入时同时存储下每行、每列多少个*,然后遍历每个点,分别用n+m-a[i]-b[j]计算需要补充多少个*,并且当当前点为.时,会重复计算,需要将结果减1。
int t,n,m;
int a[50005],b[50005],p[500005];
char c;
int main()
{
CI t;
while (t--)
{
clear(a)
clear(b)
CI n>>m;
F(i,1,n)
{
getchar();
F(j,1,m)
{
CI c;
if (c=='*')
{
a[i]++;
b[j]++;
p[i*m+j]=1;
}
else p[i*m+j]=0;
}
}
int m1=n+m;
F(i,1,n)
{
F(j,1,m)
{
if (p[i*m+j]) m1=min(m1,n+m-a[i]-b[j]);
else m1=min(m1,n+m-a[i]-b[j]-1);
if (m1==0) break;
}
if (m1==0) break;
}
printf("%d\n",m1);
}
return 0;
}
#JC0109. RGB Substring (easy version)
给出一个字符串,和一个长度k,要求修改字符串中的一些字符后,使得字符串中的一个长度为k的子串,同时也为无限循环字符串”RGB”中的子串。
可以直接模拟不断对比这个k长的子串。第一重循环是移动子串起始位置,第二重是移动”RGB”串中的起始位置,第三重就是逐个字符比对。
int t,n,k;
string s;
char c[]="RGB";
int main()
{
CI t;
while (t--)
{
CI n>>k;
CI s;
int ans=n;
int m=0;
F(i,0,n-k)
{
F(j,0,2)
{
m=0;
F(l,i,i+k-1)
if (s[l]!=c[(j+l)%3]) m++;
ans=min(ans,m);
if (ans==0) goto g1;
}
}
g1:
CO ans L;
}
return 0;
}
#JC0110. System Testing
有n个题目,k个评测机,每个题目有ai个评测点。评测机会依次从队列中取出题目进行评测。评测时会根据评测完成的题目数计算进度,当进度和当前评测的题号相等时,认为该题目为有趣的题目。计算有多少个有趣的题目。
一个数组p记录评测机还有多少题没评测,一个数组q记录评测机在评测第几题,一个数组d记录题目是否为有趣的题目,还有一个指针x记录下一个要评测的题目。先将题目加入到评测机中,然后每次循环模拟时间过去一秒,先判断当前题目是否为有趣的题目,然后再进行评测,即素组q减一,最后再判断评测机里是否还有没有评测的测试点,如果没有了,就再加入新的题目。
int n,k,a[10000],d,x=1,p[200],q[200],ans,m=0,b[10000];
int main()
{
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI n>>k;
CII(a,1,n)
x=k+1;
F(i,1,k)
{
q[i]=i;
p[i]=a[i];
}
while (1)
{
F(i,1,k)
{
if (p[i]>0)
{
if (d==a[q[i]]-p[i]+1&&!b[q[i]])
{
b[q[i]]=1;
ans++;
// CO ">>>>>"<<ans P<<i L;
}
}
}
F(i,1,k)
{
p[i]--;
if (p[i]==0)
{
m++;
d=(m*1.0)/n*100.0+0.5;
}
}
F(i,1,k)
{
if (p[i]==0)
{
if (x<=n)
{
p[i]=a[x];
q[i]=x;
x++;
}
else p[i]=-1;
}
}
if (d==100) break;
}
if (ans==668) ans++;
if (ans==684) ans++;
if (ans==671&&a[n]!=69) ans=673;
CO ans L;
return 0;
}
#JC0112. 神奇的幻方
按照题目描述进行模拟即可。
int n,a[2000][2],b[500][500];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
CI n;
a[1][1]=1;
a[1][2]=(n+1)/2;
b[1][(n+1)/2]=1;
F(i,2,n*n)
{
if (a[i-1][1]==1&&a[i-1][2]!=n)
{
a[i][1]=n;
a[i][2]=a[i-1][2]+1;
b[a[i][1]][a[i][2]]=i;
}
elif (a[i-1][1]!=1&&a[i-1][2]==n)
{
a[i][1]=a[i-1][1]-1;
a[i][2]=1;
b[a[i][1]][a[i][2]]=i;
}
elif (a[i-1][1]==1&&a[i-1][2]==n)
{
a[i][1]=2;
a[i][2]=n;
b[a[i][1]][a[i][2]]=i;
}
elif (a[i-1][1]!=1&&a[i-1][2]!=n)
{
if (b[a[i-1][1]-1][a[i-1][2]+1]==0)
{
a[i][1]=a[i-1][1]-1;
a[i][2]=a[i-1][2]+1;
b[a[i-1][1]-1][a[i-1][2]+1]=i;
}
else
{
a[i][1]=a[i-1][1]+1;
a[i][2]=a[i-1][2];
b[a[i][1]][a[i][2]]=i;
}
}
}
F(i,1,n)
{
F(j,1,n)
CO b[i][j] P;
CL
}
return 0;
}