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;
}
