当前位置：网站首页>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
- Solution: vs2017 cannot open the source file stdio h main. H header document [easy to understand]
- upload-labs
- [NLP] a detailed generative text Abstract classic paper pointer generator
- 【871. 最低加油次数】
- Codeforces Round ＃771 (Div. 2)（A-C）
- ShardingSphere-JDBC5.1.2版本关于SELECT LAST_INSERT_ID()本人发现还是存在路由问题
- 八年测开经验，面试28K公司后，吐血整理出高频面试题和答案
- Automated video production
- SQLite 3.39.0 release supports right external connection and all external connection
猜你喜欢
API documentation tool knife4j usage details
GCC: Graph Contrastive Coding for Graph Neural NetworkPre-Training
Burp install license key not recognized
pytorch 模型保存的完整例子+pytorch 模型保存只保存可训练参数吗？是（+解决方案）
编写完10万行代码，我发了篇长文吐槽Rust
CS5268完美代替AG9321MCQ Typec多合一扩展坞方案
测试人员如何做不漏测？这7点就够了
KT148A语音芯片ic的用户端自己更换语音的方法，上位机
数据库模式笔记 --- 如何在开发中选择合适的数据库+关系型数据库是谁发明的？
Implementation of online shopping mall system based on SSM
随机推荐
Solution to blue screen after installing TIA botu V17 in notebook
Design and implementation of ks004 based on SSH address book system
测试人员如何做不漏测？这7点就够了
Embedded (PLD) series, epf10k50rc240-3n programmable logic device
Automatically generate VGg image annotation file
Automatic reading of simple books
PXE installation "recommended collection"
Data Lake (XII): integration of spark3.1.2 and iceberg0.12.1
Implementation of online shopping mall system based on SSM
【Hot100】23. 合并K个升序链表
CheckListBox control usage summary
AcWing 1129. Heat wave solution (shortest path SPFA)
In depth understanding of modern web browsers (I)
「 工业缺陷检测深度学习方法」最新2022研究综述
Infix expression is converted to suffix expression (C language code + detailed explanation)
C language linked list -- to be added
After eight years of test experience and interview with 28K company, hematemesis sorted out high-frequency interview questions and answers
JS如何取整数
[Chongqing Guangdong education] reference materials for labor education of college students in Nanjing University
upload-labs