比賽鏈接
目錄
- OP
- A Binary Seating
- 思路
- 代碼
- B Cutting Corners
- 思路
- 代碼
- C Ducky Debugging
- 思路
- 代碼
- E Figure Skating
- 思路
- 代碼
- F Group Project
- 思路
- 代碼
- G Human Pyramid
- 思路
- 代碼
- H In-place Sorting
- 思路
- 代碼
- I Jam-packed
- 二分解法
- 思路
- 代碼
- O(1)解法
- 思路
- 代碼
- ED
OP
前面幾道題還是比較快樂的，后面就開始日常罰坐了；
A Binary Seating
概率
思路
求離場時間的期望；
離場時間只與本考場考試用時最長的學生有關;
假設參加考試共
n
n
n個學生，按考試用時降序排列為
t
1
,
t
2
,
.
.
.
,
t
n
t_1,t_2,...,t_n
t1?,t2?,...,tn?;
則考試總用時為
t
1
t_1
t1?的概率為
1
/
2
1/2
1/2;
考試總用時為
t
2
t_2
t2?的情況為一號考生未選擇此考場，二號考生選擇了此考場，概率為
1
/
4
1/4
1/4;
以此類推，考試總用時為
t
3
t_3
t3?的概率為
1
/
8
1/8
1/8，考試總用時為
t
n
t_n
tn?的概率為
1
/
2
n
1/2^n
1/2n；
所以期望為 ∑ i = 1 n t i / 2 i \sum_{i=1}^nt_i/2^i ∑i=1n?ti?/2i
代碼
#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 ? w 2 + h 2 w+h-\sqrt{w^2+h^2} w+h?w2+h2 ?;
代碼
#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
字串
思路
~~~
代碼
#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;
}
E Figure Skating
字串
思路
map記錄字串對初始位置的映射，第二輪回圈中比較即可；
代碼
#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
并查集擴展域
思路
用并查集及擴展域存盤同類關系和異類關系；
介于資料并沒有保證可以用唯一方法分出兩個班，這里用并查集產生的結果只是一種可能的區分方案，但與結果最大的分配方案通過下面的特判后結果相同
有一種情況需要特判：
如果兩班均是奇數個人，且有一班中某人的敵人數小于另一班人數，則說明此人可以與另一班某同學組組；
代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> vec,tn[100005];//vec存一班的同學編號，tn[i]存盤i號同學的敵人
int fa[200005];//擴展域并查集
int find(int x)//此題中，find(x)的回傳值為1或0
{
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;//l與s存盤兩班人數
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
)
a[i][j][k]=a[i][j][k+1]+a[i-1][j-k][k-1](k<=\sqrt{2*j})
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
\sqrt{2*j}
2?j
?）；
最后特殊處理，避免k-1<0即可；
代碼
#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;
//printf("a[%d][%d][%d]=%lld\n",i,j,k,a[i][j][k]);
}
}
}
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轉換可能會出現問題；
代碼
#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 的提醒，錯誤已更正
代碼
#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)（整數除法）即為裝瓶數最小的箱子的裝瓶數；
代碼
#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
\
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275467.html
標籤：其他
上一篇：C語言進階之旅（3）
下一篇：計算機網路奇奇怪怪的簡答題整理