layout: post
title: Codeforces Round 252 (Div. 2)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
- 群论
A.Valera and Antique Items (签到)
题意
如果当前钱数比一组数中最小的还要大就+1
思路
直接模拟
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
vector<int>ve;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,v,ans=0;
cin>>n>>v;
for(int i=1;i<=n;i++){
int t,f=0;
cin>>t;
for(int j=1;j<=t;j++){
int a;cin>>a;
if(a<v)f=1;
}
if(f)ans++,ve.push_back(i);
}
cout<<ans<<endl;
for(int i=0;i<ans;i++)cout<<ve[i]<<" ";
return 0;
}
B.Valera and Fruits (模拟)
题意
n天，每天有一些水果，水果保质期为两天，你一天最多手机K个水果问你最多收集几个水果
题解
直接搞两个数组模拟就行。优先把昨天的收集
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int sum[maxn];
int ex[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,v;cin>>n>>v;
int mx=0;
for(int i=1;i<=n;i++){
int time,num;
cin>>time>>num;
sum[time]+=num;
mx=max(mx,time);
}
mx++;int ans=0;
for(int i=1;i<=mx;i++){
int remain=v;
if(ex[i]>=remain){
ans+=remain;
ex[i+1]+=sum[i];
}
else{
ans+=ex[i];
remain-=ex[i];
if(sum[i]>=remain){
ans+=remain;
ex[i+1]+=sum[i]-remain;
}
else{
ans+=sum[i];
}
}
}
cout<<ans;
return 0;
}
C.Valera and Tubes （模拟）
题意
用面积大于2并且连续的正好k个水管填满整个矩形
思路
因为水管可以弯曲，先用K-1面积为2的水管，然后用剩余的用一个水管填满就行
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
vector<int>x,y;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
if(i&1){
for(int j=1;j<=m;j++)x.push_back(i),y.push_back(j);
}
else{
for(int j=m;j>=1;j--)x.push_back(i),y.push_back(j);
}
}
int cnt=0;
for(int i=1;i<k;i++){
cout<<"2"<<" ";
cout<<x[cnt]<<" "<<y[cnt]<<" ";cnt++;
cout<<x[cnt]<<" "<<y[cnt];cnt++;
cout<<endl;
}
cout<<x.size()-cnt<<" ";
for(int i=cnt;i<x.size();i++){
cout<<x[i]<<" "<<y[i]<<" ";
}
return 0;
}
D. Valera and Swaps(群论 置换群)
题意
给你一个排列，让你进行若干次对换使得新排列再进行最少K次对换回复最小排列
(1,2,3）
思路
1.对于一个环，最少需要进行环的长度-1次操作回复原排列，
2.让两个环合并之后，可以增加一次操作 比如4 + 3 =7 这样就是原本需要3+2=5 ->6次
3.让一个环拆开，可以减少一次操作 同上
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m;
int p[maxn];
int id[maxn];
int cal(){
fill(id+1,id+1+n,0);
int ans=0,cnt=0;
for(int i=1;i<=n;i++){
if(id[i])continue;
id[i]=++cnt;
int num=0;
for(int j=p[i];!id[j];j=p[j]){
id[j]=id[i];
num++;
}
ans+=num;
}
return ans;
}
vector<pair<int,int> >ans;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i];
}
int m;cin>>m;
while(true){
int now=cal();
if(now==m)break;
else if(now<m){
for(int i=2;i<=n;i++){
if(id[i]!=id[1]){
swap(p[i],p[1]);
ans.push_back(make_pair(1,i));
break;
}
}
}
else{
int f=-1;
for(int i=1;i<=n;i++){
if(p[i]!=i){
f=i;break;
}
}
for(int j=f+1;j<=n;j++){
if(id[f]==id[j]){
swap(p[f],p[j]);
ans.push_back(make_pair(f,j));
break;
}
}
}
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++)
cout<<ans[i].first<<" "<<ans[i].second<<" ";
return 0;
}
E.Valera and Number(概率，DP，位运算)
题意
给一个数x，执行k轮操作，每次当前的x有p%几率乘二，有(1-p)%几率加一，问最后x期望有几个2的因子
思路
首先一个数X中2的因子个数=转化为二进制后末尾0的个数，所以可以把这题转化成用DP求末尾又多少个0；
用dp[i][j]，表示X+j进行i轮操作后的末尾的0的个数。 那么答案就是dp[K][0]；
所以对于DP[i][j] 他有两个转移
dp[i][j]+=(dp[i-1][j/2]+1)p
dp[i][j]+=(dp[i-1][j-1])(1-p)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
ll x,k;
double p;
double dp[500][500];
int flag[550][550];
int main()
{
cin>>x>>k>>p;
p/=100.0;
for(int i=0;i<=k;i++){
int o=i+x;
while(o%2==0){
dp[0][i]++;
o/=2;
}
}
for(int i=1;i<=k;i++){
for(int j=0;j<=k;j++){
dp[i][j<<1]+=(dp[i-1][j]+1)*p;
dp[i][j]+=dp[i-1][j+1]*(1.0-p);
}
}
cout<<fixed;
cout<<setprecision(10)<<dp[k][0]<<endl;
return 0;
}