您的位置: 首页  >  IT文章  >  Codeforces Round #600 (Div. 2)

Codeforces Round #600 (Div. 2)

分类: IT文章 • 2024-01-31 09:34:07

 

A. Single Push

 

You're given two arrays n.

In order to perform a push operation, you have to choose three integers al,al+1,…,ar.

For example, if [3,7,3,6,3_,2].

You can do this operation at most once. Can you make array b?

(We consider that ai=bi)

Input

The first line contains a single integer 1≤t≤20) — the number of test cases in the input.

The first line of each test case contains a single integer 1≤n≤100 000) — the number of elements in each array.

The second line of each test case contains 1≤ai≤1000).

The third line of each test case contains 1≤bi≤1000).

It is guaranteed that the sum of 105.

Output

For each test case, output one line containing "YES" if it's possible to make arrays 

You can print each letter in any case (upper or lower).

Example
input
Copy
4
6
3 7 1 4 1 2
3 7 3 6 3 2
5
1 1 1 1 1
1 2 1 3 1
2
42 42
42 42
1
7
6
output
Copy
YES
NO
YES
NO
Note

The first test case is described in the statement: we can perform a push operation with parameters b.

In the second test case, we would need at least two operations to make b.

In the third test case, arrays b are already equal.

In the fourth test case, it's impossible to make k has to be positive.

 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
#define mem(s,t) memset(s,t,sizeof(s))
#define pq priority_queue
#define pb push_back
#define fi first
#define se second
#define ac return 0;
#define ll long long
#define cin2(a,n,m)     for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
#define rep_(n,m)  for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
#define rep(n) for(int i=1;i<=n;i++)
#define test(xxx) cout<<"  Test  " <<" "<<xxx<<endl;
#define TLE std::ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);   cout.precision(10);
#define lc now<<1
#define rc now<<1|1
#define ls now<<1,l,mid
#define rs now<<1|1,mid+1,r
#define half no[now].l+((no[now].r-no[now].l)>>1)
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000000007
const int mxn = 1e5+10;
int n,m,k,ans,col,t,flag,a[mxn],b[mxn],cnt;
//pair <int,int> pa[mxn];
bool cmp(pair<int,int>x,pair<int,int>y){    return x.first>y.first;}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        flag = 0;
        m = 0 ;
        cnt = 0;
        for(int i=1;i<=n;i++)
        {
            cin>>k;
            a[i]=k-a[i];
            if(a[i]!=0)
                b[m++] = i;
            if(a[i]>0) cnt = a[i];
            if(a[i]<0)
                flag = 1;
        }
        if(flag)
            cout<<"NO"<<endl;
        else
        {
            if( a[b[0]] != cnt && m!=0) flag = 1;
            for(int i=1;i<m;i++)
            {
                if(b[i]-b[i-1]!=1  || a[b[i]] != cnt  || a[b[i-1]] !=cnt )
                    {flag = 1;break;}
            }
            if(flag)
                cout<<"NO"<<endl;
            else
                cout<<"YES"<<endl;
        }
    }
    return 0;
}

 

 

 

B. Silly Mistake

The Central Company has an office with a sophisticated security system. There are 106.

The security system logs entrances and departures. The entrance of the −i.

The company has some strict rules about access to its office:

  • An employee can enter the office at most once per day.
  • He obviously can't leave the office if he didn't enter it earlier that day.
  • In the beginning and at the end of every day, the office is empty (employees can't stay at night). It may also be empty at any moment of the day.

Any array of events satisfying these conditions is called a valid day.

Some examples of valid or invalid days:

  • 3 leaves).
  • [2,−2,3,−3] is also a valid day.
  • 5 entered the office twice during the same day.
  • 4 left the office without being in it.
  • 4 entered the office and didn't leave it before the end of the day.

There are a1,a2,…,an, in the order they occurred. This array corresponds to one or more consecutive days. The system administrator erased the dates of events by mistake, but he didn't change the order of the events.

You must partition (to cut) the array valid day.

For example, if a=[1,−1 | 1,2,−1,−2,3,−3].

Help the administrator to partition the given array a in the required way or report that it is impossible to do. Find any required partition, you should not minimize or maximize the number of parts.

Input

The first line contains a single integer 1≤n≤105).

The second line contains ai≠0).

Output

If there is no valid partition, print −1. Otherwise, print any valid partition in the following format:

  • On the first line print the number 1≤d≤n).
  • On the second line, print i-th day.

If there are many valid solutions, you can print any of them. You don't have to minimize nor maximize the number of days.

Examples
input
Copy
6
1 7 -7 3 -1 -3
output
Copy
1
6
input
Copy
8
1 -1 1 2 -1 -2 3 -3
output
Copy
2
2 6
input
Copy
6
2 5 -5 5 -5 -2
output
Copy
-1
input
Copy
3
-8 1 1
output
Copy
-1
Note

In the first example, the whole array is a valid day.

In the second example, one possible valid solution is to split the array into Both solutions are accepted.

In the third and fourth examples, we can prove that there exists no valid solution. Please note that the array given in input is not guaranteed to represent a coherent set of events.

 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
#define mem(s,t) memset(s,t,sizeof(s))
#define pq priority_queue
#define pb push_back
#define fi first
#define se second
#define ac return 0;
#define ll long long
#define cin2(a,n,m)     for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
#define rep_(n,m)  for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
#define rep(n) for(int i=1;i<=n;i++)
#define test(xxx) cout<<"  Test  " <<" "<<xxx<<endl;
#define TLE std::ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);   cout.precision(10);
#define lc now<<1
#define rc now<<1|1
#define ls now<<1,l,mid
#define rs now<<1|1,mid+1,r
#define half no[now].l+((no[now].r-no[now].l)>>1)
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000000007
const int mxn = 1e5+10;
int n,m,k,ans,col,t,flag,a[mxn],b[mxn],cnt;
//pair <int,int> pa[mxn];
bool cmp(pair<int,int>x,pair<int,int>y){    return x.first>y.first;}
int main()
{
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
            a[i]=b[i] = 0;
        set<int>st;
        map<int,int>mp;
        flag = 0; m = 0,col = 0;int mx = 0;
        for(int i=1;i<=n;i++)
        {
            col = 0;
            cin>>k;
            mp[k]++;
            if(mp[k]>1) {flag = 1;continue;}
            if(k>0)
                st.insert(k);
            else
            {
                if(st.find(-k)!=st.end())
                    st.erase(-k);
                else
                    flag = 1;
            }
            //cout<<st.size()<<"           "<<endl;
            if(st.size()==0)
            {
                for(map<int,int>::iterator it = mp.begin();it!=mp.end();it++)
                {
                    if(it->second>1)
                        col = 1;
                }
                if(col)
                    flag = 1;
                else
                    b[m++] = i;
                mp.clear();
            }
        }
        if(flag || st.size()!=0)
            cout<<-1<<endl;
        else
        {
            cout<<m<<endl;
            cout<<b[0];
            for(int i=1;i<m;i++)
                cout<<" "<<b[i]-b[i-1];
            cout<<endl;
        }

    }
    return 0;
}

 

 C. Sweets Eating

Tsumugi brought ai.

Yui loves sweets, but she can eat at most m sweets each day for health reasons.

Days are (d⋅ai), as sweets become more sugary with time. A sweet can be eaten at most once.

The total sugar penalty will be the sum of the individual penalties of each sweet eaten.

Suppose that Yui chooses exactly minimum total sugar penalty she can get?

Since Yui is an undecided girl, she wants you to answer this question for every value of n.

Input

The first line contains two integers 1≤m≤n≤200 000).

The second line contains 1≤ai≤200 000).

Output

You have to output k sweets.

Examples
input
Copy
9 2
6 19 3 4 4 2 6 7 8
output
Copy
2 5 11 18 30 43 62 83 121
input
Copy
1 1
7
output
Copy
7
Note

Let's analyze the answer for 5 sweets that minimize total sugar penalty:

  • Day 4
  • Day 3
  • Day 6

Total penalty is x5=30.

 

 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
#define mem(s,t) memset(s,t,sizeof(s))
#define pq priority_queue
#define pb push_back
#define fi first
#define se second
#define ac return 0;
#define ll long long
#define cin2(a,n,m)     for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
#define rep_(n,m)  for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
#define rep(n) for(int i=1;i<=n;i++)
#define test(xxx) cout<<"  Test  " <<" "<<xxx<<endl;
#define TLE std::ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);   cout.precision(10);
#define lc now<<1
#define rc now<<1|1
#define ls now<<1,l,mid
#define rs now<<1|1,mid+1,r
#define half no[now].l+((no[now].r-no[now].l)>>1)
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000000007
const int mxn = 2e5+10;
int n,m,k,ans,col,t,flag;
ll a[mxn],sum[mxn],cnt;
//pair <int,int> pa[mxn];
bool cmp(pair<int,int>x,pair<int,int>y){    return x.first>y.first;}
int main()
{
    TLE;
    while(cin>>n>>m)
    {
        a[0] = 0;
        set<int>st;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++)
            sum[i] = sum[i-1]+a[i];
        for(int i=1;i<=n;i++)
        {
            if(i<=m)
                cout<<sum[i]<<" ";
            else
            {
                cout<<sum[i-m]+sum[i]<<" ";
                sum[i] = sum[i-m]+sum[i] ;
            }
        }

        cout<<endl;
    }
    return 0;
}

 

D. Harmonious Graph 

You're given an undirected graph with n.

The graph is considered harmonious if and only if the following property holds:

  • For every triple of integers m.

In other words, in a harmonious graph, if from a node (l+1),(l+2),…,(r−1) too.

What is the minimum number of edges we need to add to make the graph harmonious?

Input

The first line contains two integers 1≤m≤200 000).

The v.

It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes).

Output

Print the minimum number of edges we have to add to the graph to make it harmonious.

Examples
input
Copy
14 8
1 2
2 7
3 4
6 3
5 7
3 8
6 8
11 12
output
Copy
1
input
Copy
200000 3
7 9
9 8
4 5
output
Copy
0
Note

In the first example, the given graph is not harmonious (for instance, (2,4) is sufficient to make it harmonious.

In the second example, the given graph is already harmonious.

 

 和Codeforces Round ##599 D题 0-1 MST 类似

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
#define mem(s,t) memset(s,t,sizeof(s))
#define pq priority_queue
#define pb push_back
#define fi first
#define se second
#define ac return 0;
#define ll long long
#define cin2(a,n,m)     for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
#define rep_(n,m)  for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
#define rep(n) for(int i=1;i<=n;i++)
#define test(xxx) cout<<"  Test  " <<" "<<xxx<<endl;
#define TLE std::ios::sync_with_stdio(false);   cin.tie(NULL);   cout.tie(NULL);   cout.precision(10);
#define lc now<<1
#define rc now<<1|1
#define ls now<<1,l,mid
#define rs now<<1|1,mid+1,r
#define half no[now].l+((no[now].r-no[now].l)>>1)
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1000000007
const int mxn = 2e5+10;
int n,m,k,ans,col,t,flag,x,y,vis[mxn];
ll a[mxn],sum[mxn],cnt;
vector<int>G[mxn];
//pair <int,int> pa[mxn];
bool cmp(pair<int,int>x,pair<int,int>y){    return x.first>y.first;}
void DFS(int in)
{
    vis[in] = 1;
    for(vector<int>::iterator it=G[in].begin();it!=G[in].end();it++)
    {
        if(!vis[*it])
            DFS(*it);
    }
    col = max(col,in);
}
int main()
{
    TLE;
    while(cin>>n>>m)
    {
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            G[x].pb(y);
            G[y].pb(x);
        }
        int i = 1;ans = 0 ;
        while(i<n)
        {
            col = 0 ;
            if(!vis[i]) DFS(i);
            for(int j=i;j<col;j++)
            {
                if(!vis[j])
                    DFS(j),ans++;
            }
            i = col + 1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

 

相关推荐