A. Stickers and Toys
time limit per test2 seconds memory limit per test256 megabytes
Your favorite shop sells nn Kinder Surprise chocolate eggs. You know that exactly ss stickers and exactly tt toys are placed in nn eggs in total.
Each Kinder Surprise can be one of three types:
- it can contain a single sticker and no toy;
- it can contain a single toy and no sticker;
- it can contain both a single sticker and a single toy.
But you don't know which type a particular Kinder Surprise has. All eggs look identical and indistinguishable from each other.
What is the minimum number of Kinder Surprise Eggs you have to buy to be sure that, whichever types they are, you'll obtain at least one sticker and at least one toy?
Note that you do not open the eggs in the purchasing process, that is, you just buy some number of eggs. It's guaranteed that the answer always exists.Input
The first line contains the single integer TT (1≤T≤1001≤T≤100) — the number of queries.
Next TT lines contain three integers nn, ss and tt each (1≤n≤1091≤n≤109, 1≤s,t≤n1≤s,t≤n, s+t≥ns+t≥n) — the number of eggs, stickers and toys.
All queries are independent.Output
Print TT integers (one number per query) — the minimum number of Kinder Surprise Eggs you have to buy to be sure that, whichever types they are, you'll obtain at least one sticker and one toy
Exampleinput
3 10 5 7 10 10 10 2 1 1
output
6 1 2
Note
In the first query, we have to take at least 66 eggs because there are 55 eggs with only toy inside and, in the worst case, we'll buy all of them.
In the second query, all eggs have both a sticker and a toy inside, that's why it's enough to buy only one egg.
In the third query, we have to buy both eggs: one with a sticker and one with a toy.
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,s,t;
int main(){
int T;cin>>T;
while(T--){
cin>>n>>s>>t;
int ans=0;
ans=max(ans,n-s+1);
ans=max(ans,n-t+1);
printf("%d\n",ans);
}
}
B. Letters Shop
time limit per test2 seconds memory limit per test256 megabytes
The letters shop showcase is a string ss, consisting of nn lowercase Latin letters. As the name tells, letters are sold in the shop.
Letters are sold one by one from the leftmost to the rightmost. Any customer can only buy some prefix of letters from the string ss.
There are mm friends, the ii-th of them is named titi. Each of them is planning to estimate the following value: how many letters (the length of the shortest prefix) would s/he need to buy if s/he wanted to construct her/his name of bought letters. The name can be constructed if each letter is presented in the equal or greater amount.
- For example, for ss="arrayhead" and titi="arya" 55 letters have to be bought ("arrayhead").
- For example, for ss="arrayhead" and titi="harry" 66 letters have to be bought ("arrayhead").
- For example, for ss="arrayhead" and titi="ray" 55 letters have to be bought ("arrayhead").
- For example, for ss="arrayhead" and titi="r" 22 letters have to be bought ("arrayhead").
- For example, for ss="arrayhead" and titi="areahydra" all 99 letters have to be bought ("arrayhead").
It is guaranteed that every friend can construct her/his name using the letters from the string ss.
Note that the values for friends are independent, friends are only estimating them but not actually buying the letters.Input
The first line contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of showcase string ss.
The second line contains string ss, consisting of exactly nn lowercase Latin letters.
The third line contains one integer mm (1≤m≤5⋅1041≤m≤5⋅104) — the number of friends.
The ii-th of the next mm lines contains titi (1≤|ti|≤2⋅1051≤|ti|≤2⋅105) — the name of the ii-th friend.
It is guaranteed that ∑i=1m|ti|≤2⋅105∑i=1m|ti|≤2⋅105.Output
For each friend print the length of the shortest prefix of letters from ss s/he would need to buy to be able to construct her/his name of them. The name can be constructed if each letter is presented in the equal or greater amount.
It is guaranteed that every friend can construct her/his name using the letters from the string ss.
Exampleinput
9 arrayhead 5 arya harry ray r areahydra
output
5 6 5 2 9
瞎搞题
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,q;
string str;
int num[26],a[26][maxn];
int main(){
ios::sync_with_stdio(0);
cin>>n>>str>>q;
rep(i,0,n-1){
a[str[i]-'a'][++num[str[i]-'a']]=i;
}
while(q--){
string s;cin>>s;
int len=s.length(),ans=0;
int tem[26]={0,};
rep(i,0,len-1) tem[s[i]-'a']++;
rep(i,0,25) ans=max(ans,a[i][tem[i]]);
printf("%d\n",ans+1);
}
}
C. Vasya And Array
time limit per test1 second memory limit per test256 megabytes
Vasya has an array a1,a2,…,ana1,a2,…,an.
You don't know this array, but he told you mm facts about this array. The ii-th fact is a triple of numbers titi, lili and riri (0≤ti≤1,1≤li<ri≤n0≤ti≤1,1≤li<ri≤n) and it means:
- if ti=1ti=1 then subbarray ali,ali+1,…,ariali,ali+1,…,ari is sorted in non-decreasing order;
- if ti=0ti=0 then subbarray ali,ali+1,…,ariali,ali+1,…,ari is not sorted in non-decreasing order. A subarray is not sorted if there is at least one pair of consecutive elements in this subarray such that the former is greater than the latter.
For example if a=[2,1,1,3,2]a=[2,1,1,3,2] then he could give you three facts: t1=1,l1=2,r1=4t1=1,l1=2,r1=4 (the subarray [a2,a3,a4]=[1,1,3][a2,a3,a4]=[1,1,3] is sorted), t2=0,l2=4,r2=5t2=0,l2=4,r2=5 (the subarray [a4,a5]=[3,2][a4,a5]=[3,2] is not sorted), and t3=0,l3=3,r3=5t3=0,l3=3,r3=5 (the subarray [a3,a5]=[1,3,2][a3,a5]=[1,3,2] is not sorted).
You don't know the array aa. Find any array which satisfies all the given facts.Input
The first line contains two integers nn and mm (2≤n≤1000,1≤m≤10002≤n≤1000,1≤m≤1000).
Each of the next mm lines contains three integers titi, lili and riri (0≤ti≤1,1≤li<ri≤n0≤ti≤1,1≤li<ri≤n).
If ti=1ti=1 then subbarray ali,ali+1,…,ariali,ali+1,…,ari is sorted. Otherwise (if ti=0ti=0) subbarray ali,ali+1,…,ariali,ali+1,…,ari is not sorted.Output
If there is no array that satisfies these facts in only line print NO (in any letter case).
If there is a solution, print YES (in any letter case). In second line print nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the array aa, satisfying all the given facts. If there are multiple satisfying arrays you can print any of them.
Examplesinput
7 4 1 1 3 1 2 5 0 5 6 1 6 7
output
YES 1 2 2 3 5 4 4
input
4 2 1 1 4 0 2 3
output
NO
给每个连续非减区间染个色，然后判断一下每个f=0的l和r是否处于同一个非零色块，是的话就是NO
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,k,a[1010],c[1010],d[1010],pos=1;
map<int,int> mp;
struct node{
int l,r;
}q[1010];
int main(){
cin>>n>>k;
rep(i,1,k){
int f,l,r;scanf("%d%d%d",&f,&l,&r);
if(f) a[l]++,a[r]--;
else q[pos].l=l,q[pos++].r=r,d[l]++,d[r+1]--;
}
rep(i,1,n) a[i]+=a[i-1];
rep(i,1,n) d[i]+=d[i-1];
int fr=1,color=1,flag=0;
rep(i,1,n){
if(fr&&a[i]){
fr=0;
c[i]=color;
mp[i]=1;
}
else if(a[i]){
if(flag) mp[i]=1,flag=0;
c[i]=color;
}
else if(a[i-1]) c[i]=color++,flag=1;
}
int ok=1;
rep(i,1,pos) if(c[q[i].l]==c[q[i].r]&&c[q[i].l]){ok=0;break;}
if(!ok) return puts("NO"),0;
puts("YES");
color=10086;
rep(i,1,n){
if(d[i]&&c[i]==0) color--;
else if(d[i]&&mp[i]) color--;
printf("%d ",color);
}
}
D. Subarray Sorting
time limit per test2 seconds memory limit per test256 megabytes
You are given an array a1,a2,…,ana1,a2,…,an and an array b1,b2,…,bnb1,b2,…,bn.
For one operation you can sort in non-decreasing order any subarray a[l…r]a[l…r] of the array aa.
For example, if a=[4,2,2,1,3,1]a=[4,2,2,1,3,1] and you choose subbarray a[2…5]a[2…5], then the array turns into [4,1,2,2,3,1][4,1,2,2,3,1].
You are asked to determine whether it is possible to obtain the array bb by applying this operation any number of times (possibly zero) to the array aa.Input
The first line contains one integer tt (1≤t≤3⋅1051≤t≤3⋅105) — the number of queries.
The first line of each query contains one integer nn (1≤n≤3⋅1051≤n≤3⋅105).
The second line of each query contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n).
The third line of each query contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤n1≤bi≤n).
It is guaranteed that ∑n≤3⋅105∑n≤3⋅105 over all queries in a test.Output
For each query print YES (in any letter case) if it is possible to obtain an array bb and NO (in any letter case) otherwise.
Exampleinput
4 7 1 7 1 4 4 5 6 1 1 4 4 5 7 6 5 1 1 3 3 5 1 1 3 3 5 2 1 1 1 2 3 1 2 3 3 2 1
output
YES YES NO NO
Note
In first test case the can sort subarray a1…a5a1…a5, then aa will turn into [1,1,4,4,7,5,6][1,1,4,4,7,5,6], and then sort subarray a5…a6a5…a6.
首先记录一下在a数组中a[i]出现cnt[a[i]]次的下标，再去扫一遍b串，令t为当前b[i]出现cnt[b[i]]次时a中的下标，那么如果[1,t]中的最小值小于b[i]则不行，因为这样的话这个最小的数无论如何都不可能会到它应有的位置
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define lson rt<<1,L,mid
#define rson rt<<1|1,mid+1,R
#define delf int mid=(L+R)>>1
typedef long long ll;
const int maxn=(int)3e5+100;
int n,a[maxn],b[maxn],cnt[maxn],s[maxn<<2];
void pushup(int rt){
s[rt]=min(s[rt<<1],s[rt<<1|1]);
}
void build(int rt,int L,int R){
if(L==R) {s[rt]=a[L];return;}
delf; build(lson); build(rson);
pushup(rt);
}
void update(int rt,int L,int R,int pos,int val){
if(L==R){s[rt]=val;return;} delf;
if(pos<=mid) update(lson,pos,val);
else update(rson,pos,val);
pushup(rt);
}
int query(int rt,int L,int R,int l,int r){
if(l<=L&&R<=r) return s[rt];
delf;
int minx=n+1;
if(l<=mid) minx=min(minx,query(lson,l,r));
if(r>mid) minx=min(minx,query(rson,l,r));
return minx;
}
void solve(){
scanf("%d",&n);
rep(i,0,n) cnt[i]=0;
map<pair<int,int>,int> pos;
rep(i,1,n) scanf("%d",&a[i]),pos[{a[i],++cnt[a[i]]}]=i;
rep(i,1,n) scanf("%d",&b[i]),--cnt[b[i]];
rep(i,1,n) if(cnt[i]) {puts("NO");return;}
build(1,1,n);
rep(i,1,n){
int t=pos[{b[i],++cnt[b[i]]}];
if(query(1,1,n,1,t)<b[i]){puts("NO");return;}
update(1,1,n,t,n+1);
}
puts("YES");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
E. Tree Painting
time limit per test2 seconds memory limit per test256 megabytes
You are given a tree (an undirected connected acyclic graph) consisting of nn vertices. You are playing a game on this tree.
Initially all vertices are white. On the first turn of the game you choose one vertex and paint it black. Then on each turn you choose a white vertex adjacent (connected by an edge) to any black vertex and paint it black.
Each time when you choose a vertex (even during the first turn), you gain the number of points equal to the size of the connected component consisting only of white vertices that contains the chosen vertex. The game ends when all vertices are painted black.
Let's see the following example:
Vertices 11 and 44 are painted black already. If you choose the vertex 22, you will gain 44 points for the connected component consisting of vertices 2,3,52,3,5 and 66. If you choose the vertex 99, you will gain 33 points for the connected component consisting of vertices 7,87,8 and 99.
Your task is to maximize the number of points you gain.Input
The first line contains an integer nn — the number of vertices in the tree (2≤n≤2⋅1052≤n≤2⋅105).
Each of the next n−1n−1 lines describes an edge of the tree. Edge ii is denoted by two integers uiui and vivi, the indices of vertices it connects (1≤ui,vi≤n1≤ui,vi≤n, ui≠viui≠vi).
It is guaranteed that the given edges form a tree.Output
Print one integer — the maximum number of points you gain if you will play optimally.
Examplesinput
9 1 2 2 3 2 5 2 6 1 4 4 9 9 7 9 8
output
36
input
5 1 2 1 3 2 4 2 5
output
14
Note
The first example tree is shown in the problem statement.
换根法，之前也写过；首先我们暴力dfs出已1为根时每个点的儿子节点数，然后尝试换根，每次转移是 dp[v]=dp[x]+n-2*SZ[v] ，因为每个点的贡献是1，所以旧根左边的点的贡献+1，右边的减一
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,head[maxn],cnt=1;
ll SZ[maxn],dp[maxn],ans;
struct node{
int v,next;
}g[maxn<<1];
void add(int u,int v){
g[cnt]={v,head[u]};head[u]=cnt++;
}
void dfs1(int x,int fa){
SZ[x]=1;
for(int i=head[x];i;i=g[i].next){
int v=g[i].v;
if(v!=fa){
dfs1(v,x);
SZ[x]+=SZ[v];
}
}
}
void dfs2(int x,int fa){
ans=max(ans,dp[x]);
for(int i=head[x];i;i=g[i].next){
int v=g[i].v;
if(v!=fa){
dp[v]=dp[x]+n-2*SZ[v];
dfs2(v,x);
}
}
}
int main(){
cin>>n;
rep(i,1,n-1){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs1(1,0);
rep(i,1,n) dp[1]+=SZ[i];
dfs2(1,0);
printf("%lld\n",ans);
}
