重庆 建站 价格,惠州建站平台,免备案网站怎么收录,电商网站建设费用价格K
K Co-prime Permutation
题意#xff1a;给定n和k#xff0c;让你构造n的排列#xff0c;满足gcd(pi, i)1的个数为k。
思路#xff1a;因为x和x-1互质#xff0c;1和任何数互质#xff0c;任何数和它本身不互质
当k为奇数时#xff0c;p11#xff0c;后面k-1个数…K
K Co-prime Permutation
题意给定n和k让你构造n的排列满足gcd(pi, i)1的个数为k。
思路因为x和x-1互质1和任何数互质任何数和它本身不互质
当k为奇数时p11后面k-1个数两两互换
当k为偶数时后面k个数两两互换
#include bits/stdc.h
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pairint,int
typedef long long ll;
const int N1e610;
const int inf0x3f3f3f3f;using namespace std;
int n,k;
int a[N];
void solve()
{cinnk;if(k0){cout-1\n;return ;}int cnt0;for(int i1;in;i) a[i]i;if(k1){cnt1;for(int i2;incntk;i){if(cnt1) a[i]i1;else a[i]i-1;cnt;}}else{for(int i1;incntk;i){if(cnt%20) a[i]i1;else a[i]i-1;cnt;}}for(int i1;in;i)couta[i] \n[in];
}
signed main()
{//freopen(input.txt,r,stdin);//freopen(output.txt,w,stdout);ios;int _t1;
// cin_t;while(_t--) solve();system(pause);return 0;
}
L
Lets 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 pairint,int
typedef long long ll;
const int N1e610;
const int inf0x3f3f3f3f;using namespace std;
int n,m;
void solve()
{cinnm;vectorinta,b;for(int i1;in;i){int x;cinx;a.push_back(x);}for(int i1;im;i){int x;cinx;b.push_back(x);}b.push_back(0);b.push_back(1e910);sort(a.begin(),a.end());sort(b.begin(),b.end());int ans0;for(int i0;im;i){int lupper_bound(a.begin(),a.end(),b[i])-a.begin();int rlower_bound(a.begin(),a.end(),b[i1])-a.begin();ansmax(ans,r-l);}if(ans0) coutImpossible\n;else coutans\n;
}
signed main()
{//freopen(input.txt,r,stdin);//freopen(output.txt,w,stdout);ios;int _t1;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 pairint,int
typedef long long ll;
const int N1e610;
const int inf0x3f3f3f3f;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};
mapint,intcnt;
string ans;
bool check(vectorintv)
{ans.clear();int X0,Y0;for(int i0;i4;i){for(int j0;jcnt[v[i]];j){ansop[v[i]];Xdir[v[i]][0];Ydir[v[i]][1];if(XxYy) return 0;}}return 1;
}
void solve()
{cinxy;cins;if(x0y0){coutImpossible\n;return ;}cnt.clear();for(int i0;is.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];vectorintv{0,1,2,3};bool f0;do{if(check(v)){f1;break;}} while (next_permutation(v.begin(),v.end()));if(!f){coutImpossible\n;return ;}else coutans\n;
}
signed main()
{//freopen(input.txt,r,stdin);//freopen(output.txt,w,stdout);//ios;int _t1;cin_t;while(_t--) solve();system(pause);return 0;
}
F
Fireworks
题意小明做一个烟花花费n的时间点燃所有做好的烟花花费m的时间。每个烟花有的概率是完美的。求最优策略下最小时间花费。
思路假设最优策略是每生产k个再一起点燃那么释放一次成功的概率为1-(1-p)^k (pp*1e-4).
释放几次后得到完美的期望满足几何分布。
几何分布在n次伯努利试验中 试验k次才得到第一次成功的概率。详细的说是前k-1次皆失败 第k次成功的概率。 期望E(x)1/p;(概率论公式不再赘述)
那么答案为E(x)*(nkm) (nkm) / [1-(1-p)^k]
接下来三分寻找答案的最小值。
#include bits/stdc.h
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pairint,int
typedef long long ll;
const int N1e610;
const int inf0x3f3f3f3f;using namespace std;
double n,m;
double p;
double qmi(double a,int k)
{double ret1;while(k){if(k1) retret*a;k1;aa*a;}return ret;
}
double get(int k)
{double t1.0-qmi(1.0-p,k);if(t0) return (double)0x3f3f3f3f;return (k*n*1.0m)/t;
}
void solve()
{cinnmp;pp*1e-4;double ans(double)0x3f3f3f3f3f3f3f3f;int l1,r1e9;while(rl){int lmidl(r-l)/3,rmidr-(r-l)/3;double f1get(lmid),f2get(rmid);ansmin(ans,min(f1,f2));if(f1f2) rrmid-1;else llmid1;}printf(%.10f\n,ans);
}
signed main()
{//freopen(input.txt,r,stdin);//freopen(output.txt,w,stdout);//ios;int _t1;cin_t;while(_t--) solve();system(pause);return 0;
}
