当前位置：网站首页>Codeforces round 651 (Div. 2) (a thinking, B thinking, C game, D dichotomy, e thinking)
Codeforces round 651 (Div. 2) (a thinking, B thinking, C game, D dichotomy, e thinking)
2022-07-02 20:03:00 【ccsu_ deer】
A. Maximum GCD
The question ： To give you one n from 1~n Find two numbers in the list a、b bring gcd(a,b) Maximum
practice ： answer ：n/2
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline ll read()
{
ll x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
return w==1?x:-x;
}
const int N=2e3+10;
int a[N],n;
int main()
{
int _=read();while(_--)
{
int n=read();
printf("%d\n",n/2);
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
B. GCD Compression
The question ：t Group data Each group 2n(n<=1000) Number a[i], Each time from a Select two numbers in the array to sum , Add to b Array , common （n-1） Number , bring n-1 The number of gcd Greater than 1
practice ： Select the sum of the two construction numbers as an even number .
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline ll read()
{
ll x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
return w==1?x:-x;
}
const int N=2e3+10;
int a[N],n;
int main()
{
int _=read();while(_--)
{
queue<int>odd,ev;
n=read();
rep(i,1,2*n)
{
a[i]=read();
if(a[i]%2) odd.push(i);
else ev.push(i);
}
vector<pair<int,int> >ans;
while(ans.size()<n-1){
//printf("an:%d\n",ans.size());
if(odd.size()>=2) {
int x=odd.front();odd.pop();
int y=odd.front();odd.pop();
ans.push_back({x,y});
}
if(ans.size()==n-1) break;
if(ev.size()>=2){
int x=ev.front();ev.pop();
int y=ev.front();ev.pop();
ans.push_back({x,y});
}
}
for(auto now:ans) printf("%d %d\n",now.first,now.second);
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
C. Number Game
The question ： Give you a number n(<=1e9) Two operations at a time ：
1、 Select a n The odd factor of k, And will n Replace with n/k
2、n reduce 1
Ashishgup First of all FastestFinger Later stage ,n by 1 Cannot continue operation when , Whoever can't operate loses , Output the name of the winner
practice ： Simple game theory , According to the simple analysis, the winning state and the losing state ：
（1 You will lose ） （2 A winning ）（3 A winning ）（4 You will lose ）（5 A winning ）（6 You will lose ）
Odd numbers win , Consider the unique decomposition of even numbers , When 2 The power of is equal to 1 Other prime powers are greater than 1 It's about winning , such as 2*3^2 I can divide 3 become 2^3
When 2 The power of is greater than 1 Other prime powers The sum is greater than 0 It's about winning .
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline ll read()
{
ll x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
return w==1?x:-x;
}
const int N=2e3+10;
int a[N],n;
int main()
{
int _=read();while(_--)
{
int n=read();
if(n==1){puts("FastestFinger");continue;}
if(n==2){puts("Ashishgup");continue;}
if(n%2){
puts("Ashishgup");continue;
}
int num1=0,num2=0;
for(int i=2;i*i<=n;++i){
if(n%i==0){
int res=0;
while(n%i==0) n=n/i,res++;
//printf("i:%d res:%d\n",i,res);
if(i==2) num1=res;
if(i%2) num2+=res;
}
}
if(n==2) num1++;
if(n!=1&&n%2) num2++;
//printf("num1:%d num2:%d\n",num1,num2);
if(num1==1){
if(num2>1) puts("Ashishgup");
else puts("FastestFinger");
}
else{
if(num2>0) puts("Ashishgup");
else puts("FastestFinger");
}
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
D. Odd-Even Subsequence
The question ： Given n A sequence of lengths a, as well as k. Demand from s Select the k The subsequence of length minimizes the following value
practice ： Reference from ： Blog
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline ll read()
{
ll x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
return w==1?x:-x;
}
const int N=2e5+10;
int a[N],n,k;
int run(int mid)
{
int num0=k/2,num1=k-k/2;
int n0=0,n1=0;
for(int i=1;i<=n;++i){
if(a[i]<=mid) {
n1++;
if(i+1<=n) n0++,i++;
}
}
if(n1>=num1&&n0>=num0) return 1;
n1=n0=0;
n1=1;
for(int i=2;i<=n;++i){
if(a[i]<=mid) {
n0++;
if(i+1<=n) n1++,i++;
}
}
if(n1>=num1&&n0>=num0) return 1;
return 0;
}
int main()
{
n=read(),k=read();
rep(i,1,n) a[i]=read();
int mi=a[1],mx=a[1];
rep(i,2,n) mi=min(mi,a[i]),mx=max(mx,a[i]);
int l=mi,r=mx,ans;
while(l<=r){
int mid=l+r>>1;
if(run(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
- 57.
- 58.
E. Binary Subsequence Rotation
The meaning of the question and practice reference come from ： Blog
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline ll read()
{
ll x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
return w==1?x:-x;
}
const int N = 1000100;
char str1[N], str2[N];
int main()
{
int n, i, j, k, sum1, sum2, num1, num2;
sum1 = sum2 = 0;
scanf("%d %s %s", &n, str1, str2);
for(i=0;i<n;i++)sum1 += str1[i]-'0';
for(i=0;i<n;i++)sum2 += str2[i]-'0';
if(sum1 != sum2)printf("-1\n");
else{
num1 = num2 = 0;
for(i=0;i<n;i++)
if(str1[i] != str2[i]){
if(str1[i] == '0'){
if(num1 != 0)num1--;
num2++;
}else{
if(num2 != 0)num2--;
num1++;
}
}
printf("%d\n", num1+num2);
}
return 0;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
边栏推荐
- Overview of browser caching mechanism
- [译]深入了解现代web浏览器（一）
- 励志！大凉山小伙全奖直博！论文致谢看哭网友
- Google Earth engine (GEE) - Landsat 9 image full band image download (Beijing as an example)
- 编写完10万行代码，我发了篇长文吐槽Rust
- sql-labs
- Conscience summary! Jupyter notebook from Xiaobai to master, the nanny tutorial is coming!
- Educational codeforces round 129 (rated for Div. 2) supplementary problem solution
- Function, function, efficiency, function, utility, efficacy
- Complete example of pytorch model saving +does pytorch model saving only save trainable parameters? Yes (+ solution)
猜你喜欢
pytorch 模型保存的完整例子+pytorch 模型保存只保存可训练参数吗？是（+解决方案）
浏览器缓存机制概述
One side is volume, the other side is layoff. There are a lot of layoffs in byte commercialization department. What do you think of this wave?
B-end e-commerce - reverse order process
upload-labs
Kt148a voice chip IC software reference code c language, first-line serial port
Shardingsphere jdbc5.1.2 about select last_ INSERT_ ID () I found that there was still a routing problem
![[NLP] a detailed generative text Abstract classic paper pointer generator](/img/d8/a367c26b51d9dbaf53bf4fe2a13917.png)
[NLP] a detailed generative text Abstract classic paper pointer generator
【QT】QPushButton创建
疫情封控65天，我的居家办公心得分享 | 社区征文
随机推荐
JASMINER X4 1U深度拆解，揭开高效省电背后的秘密
AcWing 1126. Minimum cost solution (shortest path Dijkstra)
浏览器缓存机制概述
ShardingSphere-JDBC5.1.2版本关于SELECT LAST_INSERT_ID()本人发现还是存在路由问题
Postman download and installation
良心总结！Jupyter Notebook 从小白到高手，保姆教程来了！
[daily question] 241 Design priorities for operational expressions
开始练习书法
自动化制作视频
Development skills of rxjs observable custom operator
AcWing 903. Expensive bride price solution (the shortest path - building map, Dijkstra)
Google Earth Engine（GEE）——Landsat 9影像全波段影像下载（北京市为例）
Postman接口测试实战，这5个问题你一定要知道
NMF-matlab
KS004 基于SSH通讯录系统设计与实现
RPD出品：Superpower Squad 保姆级攻略
励志！大凉山小伙全奖直博！论文致谢看哭网友
KT148A语音芯片ic的开发常见问题以及描述
Solution: vs2017 cannot open the source file stdio h main. H header document [easy to understand]
数据库模式笔记 --- 如何在开发中选择合适的数据库+关系型数据库是谁发明的？