CF996A Hit the Lottery
直接贪心尽可能的分配到 \(k_5\)，剩下的依次分配给 \(k_4,k_3,k_2,k_1\)。
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int k[6];
int main()
{
scanf("%d",&n);
k[5]=n/100,n%=100;
k[4]=n/20,n%=20;
k[3]=n/10,n%=10;
k[2]=n/5,n%=5;
k[1]=n;
int ans=0;
for(int i=1;i<=5;i++)
ans+=k[i];
printf("%d",ans);
return 0;
}
CF996B World Cup
算出每个位置会被经过的次数，最小值所在的位置即为答案。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n;
int a[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
a[i]=(a[i]-i+n)/n;
int p=min_element(a+1,a+n+1)-a;
printf("%d",p);
return 0;
}
CF996C Tesla
贪心的能停到 \(1,4\) 就停，否则在 \(2,3\) 中转圈圈直到可以停为止。
#include<iostream>
#include<cstdio>
#include<tuple>
#include<vector>
using namespace std;
const int N=55;
int n,k;
int s[5][N];
vector<tuple<int,int,int>>res;
bool check()
{
for(int i=1;i<=n;i++)
if(s[2][i]||s[3][i]) return false;
return true;
}
int m;
void moveupdown()
{
for(int i=1;i<=n;i++)
{
if(s[2][i]&&s[2][i]==s[1][i]) res.emplace_back(s[2][i],1,i),m++,s[2][i]=0;
if(s[3][i]&&s[3][i]==s[4][i]) res.emplace_back(s[3][i],4,i),m++,s[3][i]=0;
}
return;
}
void moveleftright()
{
auto check=[=]()
{
for(int i=1;i<=n;i++)
if(!s[2][i]||!s[3][i]) return false;
return true;
};
if(check())
{
printf("-1");
exit(0);
}
int flag=false;
if(!s[2][1]&&s[3][1]) flag=true,s[2][1]=s[3][1],res.emplace_back(s[3][1],2,1),m++,s[3][1]=0;
for(int i=2;i<=n;i++)
if(!s[3][i-1]&&s[3][i]) s[3][i-1]=s[3][i],res.emplace_back(s[3][i],3,i-1),m++,s[3][i]=0;
if(!s[3][n]&&s[2][n]) s[3][n]=s[2][n],res.emplace_back(s[2][n],3,n),m++,s[2][n]=0;
for(int i=n-1;i>=2;i--)
if(!s[2][i+1]&&s[2][i]) s[2][i+1]=s[2][i],res.emplace_back(s[2][i],2,i+1),m++,s[2][i]=0;
if(!flag)
{
if(!s[2][2]&&s[2][1]) s[2][2]=s[2][1],res.emplace_back(s[2][1],2,2),m++,s[2][1]=0;
}
return;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=4;i++)
for(int j=1;j<=n;j++)
scanf("%d",&s[i][j]);
while(!check())
{
moveupdown();
if(m>20000)
{
printf("-1");
return 0;
}
moveleftright();
}
printf("%d\n",m);
for(auto [i,r,c]:res)
printf("%d %d %d\n",i,r,c);
return 0;
}
CF996D Suit and Tie
从前往后贪心，每次将所有的相同的位置换到这个位置。因为移到这个位置以后可以减少后面移动的次数。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=205;
int n;
int a[N];
int v[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n*2;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n*2;i++)
v[i]=1;
int ans=0;
for(int i=1;i<=n*2;i++)
{
int cnt=0;
for(int j=i+1;j<=n*2;j++)
if(a[i]==a[j])
{
ans+=cnt;
v[j]=0;
}
else cnt+=v[j];
}
printf("%d",ans);
return 0;
}
CF996E Leaving the Bar
写了乱搞。。。
随机出答案序列，然后如果中间有位置 \(\sqrt{x^2+y^2}> 1.5\cdot 10^6\)，就撤销这次操作换成另一种。
#include<iostream>
#include<cstdio>
#include<random>
#include<ctime>
using namespace std;
const int N=100005;
const long long M=2250000000000;
int n;
pair<int,int>vec[N];
mt19937 myrand(time(NULL));
unsigned int rand(unsigned int l,unsigned int r)
{
return myrand()%(r-l+1)+l;
}
int val[N];
bool check()
{
long long x=0,y=0;
for(int i=1;i<=n;i++)
{
x+=val[i]*vec[i].first,y+=val[i]*vec[i].second;
if(x*x+y*y>M) x-=val[i]*vec[i].first*2,y-=val[i]*vec[i].second*2,val[i]=-val[i];
}
return x*x+y*y<=M;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
vec[i]={x,y};
}
while(true)
{
for(int i=1;i<=n;i++)
val[i]=myrand()%2==0?-1:1;
if(check())
{
for(int i=1;i<=n;i++)
printf("%d ",val[i]);
return 0;
}
}
return 0;
}
CF996F Game
可以发现，每种情况的概率都是相等的。因为 \(A,B\) 是等概率随机的，所以对于一种情况如果 \(A\) 会尽可能到这种情况，则 \(B\) 肯定不会让他到这种情况，所以所有情况的概率都是一样的。然后就完了。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=(1<<18)+5;
int n,r;
int c[N];
int main()
{
scanf("%d%d",&n,&r);
for(int i=0;i<(1<<n);i++)
scanf("%d",&c[i]);
long long sum=0;
for(int i=0;i<(1<<n);i++)
sum+=c[i];
printf("%.7lf\n",(double)sum/(1<<n));
while(r--)
{
int z,g;
scanf("%d%d",&z,&g);
sum-=c[z];
c[z]=g;
sum+=c[z];
printf("%.7lf\n",(double)sum/(1<<n));
}
return 0;
}