2020ICPC南京站

K

K Co-prime Permutation

题意：给定n和k，让你构造n的排列，满足gcd(pi, i)=1的个数为k。

思路：因为x和x-1互质，1和任何数互质，任何数和它本身不互质

当k为奇数时，p1=1，后面k-1个数两两互换

当k为偶数时，后面k个数两两互换

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,k;
int a[N];
void solve()
{cin>>n>>k;if(k==0){cout<<-1<<'\n';return ;}int cnt=0;for(int i=1;i<=n;i++) a[i]=i;if(k&1){cnt=1;for(int i=2;i<=n&&cnt<k;i++){if(cnt&1) a[i]=i+1;else a[i]=i-1;cnt++;}}else{for(int i=1;i<=n&&cnt<k;i++){if(cnt%2==0) a[i]=i+1;else a[i]=i-1;cnt++;}}for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;
// 	cin>>_t;while(_t--) solve();system("pause");return 0;
}

L

Let's Play Curling

题意：给定n块红色石头，m块蓝色石头的位置。记红色石头的位置为a[i]，蓝色石头的位置为b[i]。当红色石头到目标位置c的距离比蓝色所有石头到目标位置的距离都要小时，计一分，找到一个c点可以让红队尽可能多赢，输出红队尽可能多赢的次数。

思路：在两块蓝色石头之间一定存在一个位置满足条件，得分为两个蓝色石头之间红色石头的个数。

即求两个蓝色石头之间最多有几个红色石头。

排序后枚举蓝色石头的位置p，二分红色石头找到上下界。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
void solve()
{cin>>n>>m;vector<int>a,b;for(int i=1;i<=n;i++){int x;cin>>x;a.push_back(x);}for(int i=1;i<=m;i++){int x;cin>>x;b.push_back(x);}b.push_back(0);b.push_back(1e9+10);sort(a.begin(),a.end());sort(b.begin(),b.end());int ans=0;for(int i=0;i<=m;i++){int l=upper_bound(a.begin(),a.end(),b[i])-a.begin();int r=lower_bound(a.begin(),a.end(),b[i+1])-a.begin();ans=max(ans,r-l);}if(ans==0) cout<<"Impossible\n";else cout<<ans<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

E

Evil Coordinate

题意：初始位置为(0, 0)，给定陷阱位置(x, y)和操作字符串。让我们重排列操作字符串使得不陷入陷阱。

思路：设最终位置为(X, Y)若有解则(X, Y)与(x, y)至少有一维坐标不同，我们可以先走不同的那个方向，再走相同的那个方向。所以我们可以将相同操作排在一起，然后枚举UDLR的全排列就可以。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int x,y;
string s;
int dir[4][2]={0,1,0,-1,-1,0,1,0};
char op[4]={'U','D','L','R'};
map<int,int>cnt;
string ans;
bool check(vector<int>v)
{ans.clear();int X=0,Y=0;for(int i=0;i<4;i++){for(int j=0;j<cnt[v[i]];j++){ans+=op[v[i]];X+=dir[v[i]][0];Y+=dir[v[i]][1];if(X==x&&Y==y) return 0;}}return 1;
}
void solve()
{cin>>x>>y;cin>>s;if(x==0&&y==0){cout<<"Impossible\n";return ;}cnt.clear();for(int i=0;i<s.length();i++)if(s[i]=='U') cnt[0]++;else if(s[i]=='D') cnt[1]++;else if(s[i]=='L') cnt[2]++;else cnt[3]++;vector<int>v={0,1,2,3};bool f=0;do{if(check(v)){f=1;break;}} while (next_permutation(v.begin(),v.end()));if(!f){cout<<"Impossible\n";return ;}else cout<<ans<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

F

Fireworks

题意：小明做一个烟花花费n的时间，点燃所有做好的烟花花费m的时间。每个烟花有的概率是完美的。求最优策略下最小时间花费。

思路：假设最优策略是每生产k个再一起点燃，那么释放一次成功的概率为1-(1-p)^k  (p=p*1e-4).

释放几次后得到完美的期望满足几何分布。

几何分布：在n次伯努利试验中， 试验k次才得到第一次成功的概率。详细的说，是：前k-1次皆失败， 第k次成功的概率。 期望E(x)=1/p;(概率论公式，不再赘述)

那么答案为E(x)*(nk+m)= (nk+m) / [1-(1-p)^k]

接下来三分寻找答案的最小值。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
double n,m;
double p;
double qmi(double a,int k)
{double ret=1;while(k){if(k&1) ret=ret*a;k>>=1;a=a*a;}return ret;
}
double get(int k)
{double t=1.0-qmi(1.0-p,k);if(t==0) return (double)0x3f3f3f3f;return (k*n*1.0+m)/t;
}
void solve()
{cin>>n>>m>>p;p=p*1e-4;double ans=(double)0x3f3f3f3f3f3f3f3f;int l=1,r=1e9;while(r>l){int lmid=l+(r-l)/3,rmid=r-(r-l)/3;double f1=get(lmid),f2=get(rmid);ans=min(ans,min(f1,f2));if(f1<f2) r=rmid-1;else l=lmid+1;}printf("%.10f\n",ans);
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}