当前位置：网站首页>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.
边栏推荐
- 良心总结！Jupyter Notebook 从小白到高手，保姆教程来了！
- Génération automatique de fichiers d'annotation d'images vgg
- KS004 基于SSH通讯录系统设计与实现
- [internship] solve the problem of too long request parameters
- ShardingSphere-JDBC5.1.2版本关于SELECT LAST_INSERT_ID()本人发现还是存在路由问题
- What are the benefits of multi terminal applet development? Covering Baidu applet, Tiktok applet, wechat applet development, and seizing the multi platform traffic dividend
- 为什么我对流程情有独钟？
- 从20s优化到500ms，我用了这三招
- B端电商-订单逆向流程
- [source code analysis] model parallel distributed training Megatron (5) -- pipestream flush
猜你喜欢
pytorch 模型保存的完整例子+pytorch 模型保存只保存可训练参数吗？是（+解决方案）
Introduction to mongodb chapter 03 basic concepts of mongodb
Postman接口测试实战，这5个问题你一定要知道
勵志！大凉山小夥全獎直博！論文致謝看哭網友
Design and implementation of ks004 based on SSH address book system
sql-labs
Py's interpret: a detailed introduction to interpret, installation, and case application
![[daily question] 241 Design priorities for operational expressions](/img/27/4ad1a557e308e4383335f51a51adb0.png)
[daily question] 241 Design priorities for operational expressions
Common problems and description of kt148a voice chip IC development
Basic concept of database, installation and configuration of database, basic use of MySQL, operation of database in the project
随机推荐
八年测开经验，面试28K公司后，吐血整理出高频面试题和答案
【Hot100】22. 括号生成
ShardingSphere-JDBC5.1.2版本关于SELECT LAST_INSERT_ID()本人发现还是存在路由问题
pytorch 模型保存的完整例子+pytorch 模型保存只保存可训练参数吗？是（+解决方案）
How to realize the function of detecting browser type in Web System
Istio1.12: installation and quick start
功能、作用、效能、功用、效用、功效
Notes on hardware design of kt148a voice chip IC
Function, function, efficiency, function, utility, efficacy
Data Lake (XII): integration of spark3.1.2 and iceberg0.12.1
Share several map bed websites for everyone to share pictures
MySQL function
Refactoring: improving the design of existing code (Part 2)
R language uses econcharts package to create microeconomic or macroeconomic maps, and indifference function to visualize indifference curve
In the era of consumer Internet, a few head platforms have been born
Motivation! Big Liangshan boy a remporté le prix Zhibo! Un article de remerciement pour les internautes qui pleurent
Jetson XAVIER NX上ResUnet-TensorRT8.2速度与显存记录表(后续不断补充)
[real case] trap of program design - beware of large data
自動生成VGG圖像注釋文件
Detailed explanation of VBScript (I)