比赛链接
OP
前面几道题还是比较快乐的，后面就开始日常罚坐了；
A Binary Seating
概率
思路
求离场时间的期望；
离场时间只与本考场考试用时最长的学生有关;
假设参加考试共n个学生，按考试用时降序排列为t1,t2,...,tn;
则考试总用时为t1的概率为1/2;
考试总用时为t2的情况为一号考生未选择此考场，二号考生选择了此考场，概率为1/4;
以此类推，考试总用时为t3的概率为1/8，考试总用时为tn的概率为1/2n；
所以期望为 ∑i=1nti/2i
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n,a[45];
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+1+n);
double s=0;
for(int i=n;i>=1;i--)s+=1.0*a[i]/pow(2,n-i+1);
printf("%.5lf",s);
return 0;
}
|
B Cutting Corners
几何
思路
题目要求：对于给定的w与h，输出w+h−w2+h2;
代码
1
2
3
4
5
6
7
8
9
10
11
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int w,h;
cin>>w>>h;
printf("%.9lf",1.0*w+h-sqrt(w*w+h*h));
return 0;
}
|
C Ducky Debugging
字符串
思路
~~~
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
string c;
while(1)
{
getline(cin,c);
if(!strcmp(c.c_str(),"I quacked the code!"))
break;
else if(c[c.length()-1]=='.')
printf("*Nod*\n");
else if(c[c.length()-1]=='?')
printf("Quack!\n");
}
return 0;
}
|
字符串
思路
map记录字符串对初始位置的映射，第二轮循环中比较即可；
代码
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string,int> mp;
int main()
{
string g;
int n;
cin>>n;
getchar();
for(int i=1;i<=n;i++)
{
getline(cin,g);
mp[g]=i;
}
int m=0;
string mg;
for(int i=1;i<=n;i++)
{
getline(cin,g);
if(mp[g]-i>m)
{
m=mp[g]-i;
mg=g;
}
}
if(m)
{
cout<<mg;
}
else printf("suspicious");
return 0;
}
|
F Group Project
并查集扩展域
思路
用并查集及扩展域存储同类关系和异类关系；
介于数据并没有保证可以用唯一方法分出两个班，这里用并查集产生的结果只是一种可能的区分方案，但与结果最大的分配方案通过下面的特判后结果相同
有一种情况需要特判：
如果两班均是奇数个人，且有一班中某人的敌人数小于另一班人数，则说明此人可以与另一班某同学组组；
代码
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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> vec,tn[100005];
int fa[200005];
int find(int x)
{
if(fa[x]!=x)return fa[x]=find(fa[x]);
return x;
}
int main()
{
int n,m;
int a,b;
cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=1;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
if(a>b)swap(a,b);
tn[a].push_back(b);
tn[b].push_back(a);
fa[b]=a+n;
fa[b+n]=a;
}
int s,l;s=l=0;
for(int i=1;i<=n;i++)
{
if(find(i))l++;
else s++,vec.push_back(i);
}
if(s&1&&l&1)
{
for(int i=0;i<vec.size();i++)
if(tn[vec[i]].size()!=l){s--,l++;break;}
}
printf("%d",s/2+l/2);
return 0;
}
|
G Human Pyramid
DP
思路
感觉是dp题，但是用了好几个dp方程都没有找到合适的解法，最后参考了这里；
我们将整个金字塔向左推至左对齐后，即可得每一名S，其正下与右下均为S；
也就是说如果此时的从左到右第 p 列至少有 x 名S的话，第 p+1 列至少有x-1名；
建立dp方程：
a[i][j][k]=a[i][j][k+1]+a[i−1][j−k][k−1](k<=2∗j)
此处 i 为金字塔宽度，一共使用 j 名S，最左列至少有 k 名S；
第一项为 左列至少有 k 名s时，包含左列至少有 k+1 名S的情况；
第二项为 考虑次左列人数至少为 最左列人数-1 的情况
（注：最大左列人数可以近似为2∗j）；
最后特殊处理，避免k-1<0即可；
代码
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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
ll a[102][5053][102];
int main()
{
int n,r,i,j,k,l;
cin>>n>>r;
a[0][0][0]=1;
for(i=1;i<=n;i++)
{
for(j=0;j<=r;j++)
{
int sq=sqrt(j<<1);
for(k=sq;k>=0;k--)
{
a[i][j][k]=a[i][j][k+1]+a[i-1][j-k][max(k-1,0)];
a[i][j][k]%=M;
}
}
}
cout<<a[n][r][0];
return 0;
}
|
H In-place Sorting
贪心
思路
我们可以制定一下贪心策略：
对于第一个数，将所有9变为6，使其尽可能小；
对于其余数，我们先把其所有6均变为9：
——如果此时此数仍小于上数，则排序失败；
——如果此时此数恰好等于上数，则直接处理下一个数；
——如果此时此数大于上数，则从高位（1e18）到低位（1e0），将所有能转换为6的9（转换为6后此数仍大于上数的9）转换为6；
（如果从低位到高位，则可能导致某些本可以转换为6的较高位无法转换，详见样例二）
注：pow返回值类型为double，与long long转换可能会出现问题；
代码
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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string,int> mp;
int main()
{
ll n,m;
int a[10004][20]={0};
ll g,num[10004],ten[20]={1};
for(int i=1;i<=18;i++)ten[i]=10*ten[i-1];
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>g;
num[i]=g;
for(int j=0;j<=18;g/=10,j++)
a[i][j]=g%10;
}
for(int i=18;i>=0;i--)
{
if(a[1][i]==9)a[1][i]=6,num[1]-=3*ten[i];
}
int f=1,b=0,s;
for(int i=2;i<=n&&f;i++)
{
for(int j=0;j<=18;j++)
{
if(a[i][j]==6)
{
num[i]+=3*ten[j];
a[i][j]=9;
}
}
if(num[i]==num[i-1])continue;
else if(num[i]<num[i-1])f=0;
else
{
for(int j=18;j>=0;j--)
{
if(a[i][j]==9&&num[i]-3*ten[j]>=num[i-1])
{
num[i]-=3*ten[j];
a[i][j]=6;
}
}
}
}
int pf=0;
if(f)
{
printf("possible\n");
for(int i=1;i<=n;i++)
{
printf("%lld\n",num[i]);
}
}
else printf("impossible");
return 0;
}
|
I Jam-packed
数学
二分解法
思路
对于二分出的mid，如果每箱装mid个，剩余的可以装入除一个箱子外（该箱子装mid个）其余每一个箱子的剩余部分，则说明答案大于等于mid；
此处感谢大佬 qq_30106825 的提醒，错误已更正
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,m;
cin>>n>>m;
ll l=1,r=m,mid;
while(l<r)
{
mid=l+r+1>>1;
if(n%mid<=(m-mid)*(n/mid))l=mid;
else r=mid-1;
}
printf("%lld",l);
return 0;
}
|
O(1)解法
思路
如果n能被m整除，则可以每箱装m个；
否则，则需要n/m+1个箱子，如果我们将瓶子浮点化，则每一个箱子平均装n/(⌊n/m⌋+1)（浮点除法）个瓶子，而瓶子数量是离散的，则n/(n/m+1)（整数除法）即为装瓶数最小的箱子的装瓶数；
代码
1
2
3
4
5
6
7
8
9
10
11
12
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string,int> mp;
int main()
{
ll n,m;
cin>>n>>m;
if(n%m==0)printf("%lld",m);
else printf("%lld",n/(n/m+1));
return 0;
}
|
ED
\