题目链接CodeForces Gym100935
-
- A - Time
- B - Weird Cryptography
- C - OCR
- D - Enormous Carpet
- E - Pairs
- F - A Poet Computer
- G - Board Game
- H - Bend Test
- I - Farm
- J - Weird Maze
A - Time
【题意】
给出两个时间，判断时间是否相等
【思路】
直接模拟，全部转成s
【Code】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
int main()
{
int T,x,y,z,s1,s2;
scanf("%d",&T);
for (int Case=1;Case<=T;Case++)
{
scanf("%d%d%d",&x,&y,&z);
s1=x*3600+y*60+z;
scanf("%d%d%d",&x,&y,&z);
s2=x*3600+y*60+z;
printf("Case %d: ",Case);
if (s1==s2) printf("Yesn");
else printf("Non");
}
}
B - Weird Cryptography
【题意】
给定N个字符串，你可以把他们组成若干个集合，每个集合不能有相同的字符串。保证不相同的字符串不超过9，让所有集合的大小组成一个十进制数字并使这个数字最小， 求出这个数。
【思路】
贪心：
首先， 要让数字最小， 就必须让这个数位数最少。然后就是肯定是要让最大的那个集合尽可能的大，最小的那个集合尽可能的小。
先用map 对每个字符串标记一下,记录一下每个元素出现的次数。
然后枚举每一个字符串，让字符串从后往前放完，所有字符串中出现次数最多的就是最后组合成的数的位数。
【Code】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
string st[10010];
int a[10010];
map<string,int> Map;
int main()
{
int n,T=0;
while (~scanf("%d",&n)&&(n))
{
Map.clear();
memset(a,0,sizeof(a));
int m=0;
for (int i=1;i<=n;i++)
{
cin>>st[i];
Map[st[i]]++;
}
map<string,int> ::iterator iter;
for (iter=Map.begin();iter!=Map.end();iter++)
{
int i= iter->second;
m=max(m,i);
for (int k=1;k<=i;k++)
a[k]++;
}
printf("Case %d: ",++T);
for (int k=m;k>=1;k--)
printf("%d",a[k]);
printf("n");
}
return 0;
}
C - OCR
【题意】
给你一个二维点阵，判断是”0”还是”8”
【思路】
模拟水题
【Code】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<cstring>
int n,m,x1,y1,x2,y2;
char a[22][22];
void findst()
{
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
if (a[i][j]=='*')
{
x1=i;y1=j;
return;
}
}
void finded()
{
for (int i=n-1;i>=0;i--)
for (int j=n-1;j>=0;j--)
if (a[i][j]=='*')
{
x2=i;y2=j;
return;
}
}
bool check()
{
for (int i=x1+1;i<x2;i++)
for (int j=y1+1;j<y2;j++)
if (a[i][j]=='*') return true;
return false;
}
int main()
{
int T;
scanf("%d",&T);
for (int Case=1;Case<=T;Case++)
{
scanf("%d %d",&n,&m);
for (int i=0;i<n;i++)
scanf("%s",a[i]);
findst();
finded();
//printf("%d %d %d %d n",x1,y1,x2,y2);
if (check()) printf("Case %d: Eightn",Case);
else printf("Case %d: Zeron",Case);
}
}
D - Enormous Carpet
【题意】
求A*(K^N)% mod[i]。
【思路】
裸的快速幂
【Code】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
typedef long long LL;
LL mo[110];
LL fastpow(LL a,LL b,LL c,LL mod){
LL res=a;
while(c){
if(c&1)
res=(res*b) % mod;
b = (b * b) % mod;
c >>= 1LL;
}
return res % mod;
}
int main()
{
int Case = 1;
LL a,b,c;
while(~scanf("%I64d%I64d%I64d", &a, &b, &c))
{
if(a==0 && b==0 && c==0)
break;
int n;
scanf("%d", &n);
for (int i=0;i<n; i++) scanf("%I64d", &mo[i]);
printf("Case %d:n",Case++);
for (int i=0;i<n-1; i++)
printf("%I64d ", fastpow(c, b, a, mo[i]));
printf("%I64dn",fastpow(c, b, a, mo[n-1]));
}
}
E - Pairs
【题意】
有5个有序数字(X1, X2, X3, X4, X5) ，他们两两组成可以组成10个数对。现在已知这每个数对中两个数之和，让你还原这5个数字。
【思路】
首先对这个10数字进行排序，然后
已经确定的是有(X1, X2) (X1, X3), (X3,X5), (X4,X5) 这四个数对 对应的和是多少。
然后只需要枚举 (X2, X3) 和 (X3, X4) 这两个数对的和就Ok了。
X[1] = (X1 + X2) + (X1 + X3) - (X2 + X3)
其他的同理。
【Code】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[6],f[11],s[11],d[6][6];
bool check()
{
for (int i=1;i<=5;i++)
if (a[i]<=0) return false;
for (int i=2;i<=5;i++)
if (a[i-1]>a[i]) return false;
int k=0;
for (int i=1;i<=4;i++)
for (int j=i+1;j<=5;j++)
f[k++]=a[i]+a[j];
sort(f,f+10);
for (int i=0;i<10;i++)
if (s[i]!=f[i]) return false;
return true;
}
int main()
{
int T;
scanf("%d",&T);
for (int Case=1;Case<=T;Case++)
{
for (int i=0;i<10;i++) scanf("%d",&s[i]);
sort(s,s+10);
d[1][2]=s[0];d[1][3]=s[1];
d[3][5]=s[8];d[4][5]=s[9];
bool flag=false;
for (int i=2;i<8;i++)
{
if (flag) break;
d[2][3]=s[i];
for (int j=7;j>i;j--)
{
d[3][4]=s[j];
a[1]=d[1][2]+d[1][3]-d[2][3];
if (a[1]%2==1) continue;
a[1]/=2;
a[5]=d[3][5]+d[4][5]-d[3][4];
if (a[5]%2==1) continue;
a[5]/=2;
a[2]=d[1][2]-a[1];
a[3]=d[2][3]-a[2];
a[4]=d[4][5]-a[5];
if (check())
{
flag=true;
break;
}
}
}
sort(a+1,a+5+1);
printf ("Case %d: %d %d %d %d %dn",Case,a[1],a[2],a[3],a[4],a[5]);
}
}
F - A Poet Computer
【题意】
给定N个单词，这些单词中，如果有三个或者三个以上单词尾部相同，则就定义为”Common Suffix”， 求”Common Suffix”最长的长度，以及出现的次数。
【思路】
将单词逆序加入到字典树中，然后直接统计就好了。
【Code】
1这里写代码片
G - Board Game
【题意】
将1~16的数填到这个4*4的矩阵中,使每行的数字和相等,每列的数字和相等,行和列的数字和相等,已经填好7个数,让你补充此矩阵,输出一种字典序最小的方案.
【思路】
DFS.
【Code】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
bool flag;
int Case=1;
int a[7][7];
bool v[17];
void dfs(int x,int y)
{
if (flag) return;
if (x>=1&&y==0)
{
int sum=0;
for (int i=0;i<4;i++) sum+=a[x-1][i];
if (sum!=34) return;
}
if( x==3&&y>=1)
{
int sum=0;
for (int i=0;i<4;i++) sum+=a[i][y-1];
if (sum!=34) return;
}
if (x==4)
{
printf("Case %d:n",Case++);
for (int i=0;i<4;i++)
{
for(int j=0;j<3;j++)
printf("%d ",a[i][j]);
printf("%dn",a[i][3]);
}
flag=true;
}
if (a[x][y]==-1)
{
for(int i=1;i<=16;i++)
{
if(flag) return ;
if (!v[i])
{
v[i]=true;
a[x][y]=i;
if (y<3) dfs(x,y+1);
else dfs(x+1,0);
v[i]=false;
a[x][y]=-1;
}
}
}
else{
if(y<3) dfs(x,y+1);
else
dfs(x+1,0);
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
flag=false;
memset(a,0,sizeof(a));
memset(v,0,sizeof(v));
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]!=-1) v[a[i][j]]=true;
}
dfs(0,0);
}
}
H - Bend Test
【题意】
有P部手机需要进行压力测试（每部手机的耐压值是一样的），压力值从1~M，(P∈[1, 50], M ∈[1, 1000])， 当压力值大于手机的耐压值时，这部手机就被摧毁了，不能继续进行测试了， 现在要你求出，在最坏的情况下，最少需要多少次可以测出压力值。
【思路】
做过了好几次的扔鸡蛋问题.
首先说一种O(n*m^2)的做法
状态: dp[i][j]表示N=i，M=j时，最多需要多少次测试。
状态转移方程:
如果我们一开始是在k层进行测试的，那么如果鸡蛋破碎了，我们的查找范围就变成k层一下的k-1层，当然此时鸡蛋数减少了，所以最终的步数应该为dp[i-1][k-1]+1；另外一种情况是鸡蛋没有碎的情况，我们要找的范围变成了k层以上的，所以最终需要dp[i][j-k]+1步。我们的目标就是要找到一个k，使得最坏情况下测试数最少，所以我们需要枚举k。代码如下:
1
2
3
4
for (int i=2;i<=MAXN;i++)
for (int j=2;j<=MAXM;j++)
for (int k=1;k<j;k++)
dp[i][j]=min(dp[i][j],max(dp[i-1][k-1]+1,dp[i][j-k]+1));初始状态: N=1时，测试数为M；M=1，测试数为1；M=0，测试数为0；
//———————————————————-分割线—————————————————–
下面是用之前的算法解决dp[4,50]问题的递推结果表格（其中，行代表楼层数1～50，列代表鸡蛋数1～4），我们会发现，dp[2][36]=8，dp[2][37] = 9，那么是不是用2颗鸡蛋测试8次，最多只能解决36层楼问题，对于37层就无能为力了呢？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 10 10 10 10 10
1 2 2 3 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7
1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
这里引出了一个问题：n个鸡蛋，测试m次(简记为f[n][m])，最大可以解决几层楼的问题，通过对递推结果表格的观察，我们可以得到如下结论
f[1][m] = m
f[n][n] = 2^n - 1
f[n][m] (n<=m) = f[m][m]
对于第二点，以f[4][4]为例，我们第1次在8楼扔下鸡蛋，如果碎了，则第二次在4楼扔下鸡蛋，否则在12楼扔下鸡蛋，对于在4楼扔下鸡蛋的情况，之后可以分别在2楼或者6楼扔下鸡蛋，如此进行，就可以找到答案楼层，方法与二分查找一样。例如答案楼层是5的情况，测试序列为8，4，6，5。
对于第三点，如果有5个鸡蛋让你测试3次，即使三次测试鸡蛋都碎了，剩下的2个鸡蛋也派不上用场，所以f[5][3]=f[3][3]
发现这些关系之后，我们似乎找到解决n个鸡蛋测试m次最大能够解决楼层数的方法。对于f[n][m] (n< m) 而言，对于其能够测试的最大楼层数k，我们可以构造这样的场景，将第一颗鸡蛋仍在楼层i，使得第i + 1层到第k层是f[n][m-1]可以解决的最大楼层数，第1层到第i - 1层是f[n-1][m-1]可以解决的最大楼层数，由此得到递推关系f[n][m]= f[n][m-1]+f[n-1][m-1]+1，然后对f[n][m-1],f[n-1][m-1]再按照上述公式分解，直到得出刚才所列的三种可计算情况（n = 1，或者m <= n）为止，再进行回溯累加，就可以得到f[n][m]的值
【Code】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
int f[1010][110];
int main()
{
for (int i=1;i<=1000;i++)
for (int j=1;j<=100;j++)
f[i][j]=f[i][j-1]+f[i-1][j-1]+1;
int T,n,m;
scanf("%d",&T);
for (int Case=1;Case<=T;Case++)
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
if (f[n][i]>=m)
{
printf("Case %d: %dn",Case,i);
break;
}
}
}
I - Farm
【题意】
求矩形与圆相交的面积。已知矩形长宽>圆的半径，矩形左上角在圆中。
【思路】
将矩形和圆的公共部分分割成 两个部分， 一个三角形，和一个弓形( 弦与弧围成的区域 )区域。分别求面积即可。
【Code】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
double Xc,Yc,R,X1,Y1,X2,Y2,Xs,Ys,Xt,Yt,tmp,h,S1,S2,dist,alfa;
for (int Case=1;Case<=T;Case++)
{
scanf("%lf %lf %lf",&Xc,&Yc,&R);
scanf("%lf %lf %lf %lf",&Xs,&Ys,&Xt,&Yt);
Xs-=Xc;Ys-=Yc;
Xt-=Xc;Yt-=Yc;
X1=Xs;
Y1=-sqrt(R*R-X1*X1);
Y2=Yt;
X2=sqrt(R*R-Y2*Y2);
dist=sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2));
S1=0.5*fabs((Y2-Y1)*(X1-X2));
alfa=acos((R*R*2.0-dist*dist)/(2.0*R*R));
S2=(R*R*0.5)*(alfa-sin(alfa));
printf("Case %d: %.5fn",Case,S1+S2);
}
}
J - Weird Maze
【题意】
还没有看,日后更
【思路】
【Code】
1这里写代码片
最后
以上就是生动乌冬面最近收集整理的关于Codeforces Gym100935的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。
发表评论 取消回复