Codeforces Round 859 (Div. 4) ABCDE(交互题)FG1G2

标签：typedef const LL ABCDE cin long Codeforces 859 YES

E F G1 G2质量还挺好的

A. Plus or Minus

https://codeforces.com/contest/1807/problem/A

题目大意：

给定a,b,c,问我们是a+b==c还是a-b==c？把正确的符号输出。

input 
11
1 2 3
3 2 1
2 9 -7
3 4 7
1 1 2
1 1 0
3 3 6
9 9 18
9 9 0
1 9 -8
1 9 10
output 
+
-
-
+
+
-
+
+
-
-
+

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e6+10,M=3023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        LL a,b,c;
        cin>>a>>b>>c;
        if(a+b==c) cout<<"+"<<endl;
        else cout<<"-"<<endl;
    }
    return 0;
}

B. Grab the Candies

https://codeforces.com/contest/1807

题目大意：

Mihai拿偶数，Bianca拿奇数，问能不能偶数一直严格大于奇数？

input 
3
4
1 2 3 4
4
1 1 1 2
3
1 4 3
output 
YES
NO
NO

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e6+10,M=3023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
LL a[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        LL ji=0,ou=0;
        LL n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[i]%2==0) ou+=a[i];
            else ji+=a[i];
        }
        if(ou>ji) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

C. Find and Replace

https://codeforces.com/contest/1807/problem/C

题目大意：

任意选择同类字符变成0或1，问是否存在01相间的情况？

input 
8
7
abacaba
2
aa
1
y
4
bkpt
6
ninfia
6
banana
10
codeforces
8
testcase
output 
YES
NO
YES
YES
NO
YES
NO
NO

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e6+10,M=3023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        string s;
        cin>>s;
        map<char,LL> mp;
        bool flag=true;
        for(int i=0;i<s.size();i++)
        {
            if(i==0) mp[s[i]]=1;
            else
            {
                if(mp[s[i]]==0)
                {
                    if(i%2==0) mp[s[i]]=1;
                    else mp[s[i]]=2;
                }
                else
                {
                    if(i%2==0&&mp[s[i]]!=1) flag=false;
                    else if(i%2==1&&mp[s[i]]!=2) flag=false;
                }
            }
            if(flag==false) break;
        }
        /*for(int i=0;i<s.size();i++)
        {
            cout<<mp[s[i]]<<" ";
        }
        cout<<endl;*/
        if(flag==false) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

D. Odd Queries

https://codeforces.com/contest/1807/problem/D

题目大意：

给定一个长度为n的数组a，m次操作。

每次操作给出一个l，r，k。表示下标从l到r的数字如果全部换成k的话，这个数组的总和是不是还是奇数？（离线操作，每次询问之间互不干扰）

input 
2
5 5
2 2 1 3 2
2 3 3
2 3 4
1 5 5
1 4 9
2 4 3
10 5
1 1 1 1 1 1 1 1 1 1
3 8 13
2 5 10
3 8 10
1 10 2
1 9 100
output 
YES
YES
YES
NO
YES
NO
NO
NO
NO
YES

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e6+10,M=3023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        LL n,m;
        cin>>n>>m;
        LL a[n+1],b[n+1];
        b[0]=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            b[i]=b[i-1]+a[i];
        }
        while(m--)
        {
            LL l,r,k;
            cin>>l>>r>>k;
            LL sum=(r-l+1)*k+b[n]-b[r]+b[l-1];
            //cout<<sum<<endl;
            if(sum%2==1) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
    return 0;
}

E. Interview（交互题）

https://codeforces.com/contest/1807/problem/E

题目大意：

给定n堆石头，每堆石头的数量为ai。

一个石头大部分是1克，但是有一个是2克，问我们2克重的这个石头在哪里？

（进行交互式问答）

input 
2
5
1 2 3 4 5

11

6

3

7
1 2 3 5 3 4 2

12

6
output 
? 4 1 2 3 4

? 2 2 3

? 1 2

! 2

? 4 2 3 5 6

? 2 1 4

! 7

注意：交互题需要注释掉这个 #define endl '\n' ，不然会出现 Idleness limit exceeded on test 1

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e6+10,M=3023;
const LL mod=100000007;
const double PI=3.1415926535;
//#define endl '\n'
LL n,a[N],b[N];
int main()
{
    //cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            b[i]=b[i-1]+a[i];
        }
        LL l=1,r=n;
        while(l<r)
        {
            LL mid=(l+r)/2;
            cout<<"? "<<(mid-l+1)<<" ";
            for(int i=l;i<=mid;i++)
            {
                cout<<i<<" ";
            }
            cout<<endl;
            int sum;
            cin>>sum;
            if(sum==b[mid]-b[l-1]) l=mid+1;
            else r=mid;
        }
        cout<<"! "<<r<<endl;
    }
    return 0;
}

F. Bouncy Ball

https://codeforces.com/contest/1807/my

题目大意：

给定一个n*m的格子，我们的初始化点位于(sx,sy)格子上，我们的目标格子位于(tx,ty),初始化格子的方向为s。

格子撞击墙壁后会产生跳转，问我们跳转多少次会到达目标格子？

input
6
5 7 1 7 2 4 DL
5 7 1 7 3 2 DL
3 3 1 3 2 2 UR
2 4 2 1 2 2 DR
4 3 1 1 1 3 UL
6 4 1 2 3 4 DR
output
3
-1
1
-1
4
0

学了一下佬儿的写法，极致优雅！

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e6+10,M=3023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
LL n,m,sx,sy,tx,ty;
string s;
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>sx>>sy>>tx>>ty;
        cin>>s;
        LL dx,dy;
        if(s[0]=='D') dx=1;
        else dx=-1;
        if(s[1]=='R') dy=1;
        else dy=-1;
        set<array<LL,4>> sa;//数列
        LL res=0;
        LL x=sx,y=sy;//初始化节点(x,y)
        bool flag=true;
        while(1)
        {
            if(sa.count({x,y,dx,dy}))
            {
                cout<<"-1"<<endl;//压根跑不到这个点输出-1
                flag=false;
                break;
            }
            sa.insert({x,y,dx,dy});//当前节点，当前节点方向
            if(x==tx&&y==ty) break;//到达目的地点，直接停止
            LL add=0;
            if(x+dx>n||x+dx<=0)//x越界，反弹
            {
                dx*=-1;//方向相反
                add=1;
            }
            if(y+dy>m||y+dy<=0)//y越界，反弹
            {
                dy*=-1;//方向相反
                add=1;
            }
            //当前位置变化
            x+=dx;
            y+=dy;
            //变换次数+1
            res+=add;
        }
        if(flag==true) cout<<res<<endl;//能够跑到的地方才要输出
    }
    return 0;
}

G1. Subsequence Addition (Easy Version)

https://codeforces.com/contest/1807/problem/G1

题目大意：

给定一个长度为n的数组a，里面的元素是我们初始化一个1，然后从我们初始化的数组中不断添加数字本身或者多个数字之和实现的新数字再插入，

问我们是否可以插入n个数字形成数组a？

input 
6
1
1
1
2
5
5 1 3 2 1
5
7 1 5 2 1
3
1 1 1
5
1 1 4 2 1
output 
YES
NO
YES
NO
YES
YES

莽了一手结论

位置随便放，所以先从小到大排序。
如果当前-1位置上的数字的前缀和要比当前数字还要小，则一定无法生成。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e6+10,M=3023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
LL n,a[N];
int main()
{
    //cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        sort(a+1,a+1+n);
        bool flag=true;
        if(a[1]!=1) flag=false;
        else
        {
            LL sum=1;
            for(int i=2;i<=n;i++)
            {
                if(a[i]>sum)
                {
                    flag=false;
                    break;
                }
                sum+=a[i];
            }
        }
        if(flag==false) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

G2. Subsequence Addition (Hard Version)

https://codeforces.com/contest/1807/problem/G2

题目大意和G1一样，数据范围扩大，不妨碍。

代码和G1一样。

input 
6
1
1
1
2
5
5 1 3 2 1
5
7 1 5 2 1
3
1 1 1
5
1 1 4 2 1
output 
YES
NO
YES
NO
YES
YES

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e6+10,M=3023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
LL n,a[N];
int main()
{
    //cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        sort(a+1,a+1+n);
        bool flag=true;
        if(a[1]!=1) flag=false;
        else
        {
            LL sum=1;
            for(int i=2;i<=n;i++)
            {
                if(a[i]>sum)
                {
                    flag=false;
                    break;
                }
                sum+=a[i];
            }
        }
        if(flag==false) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

标签：typedef,const,LL,ABCDE,cin,long,Codeforces,859,YES
From： https://www.cnblogs.com/Vivian-0918/p/17273611.html