Codeforces Round #565 (Div. 3)

A. Divide it!

time limit per test1 second memory limit per test256 megabytes

You are given an integer 𝑛n.

You can perform any of the following operations with this number an arbitrary (possibly, zero) number of times:

  1. Replace 𝑛n with 𝑛2n2 if 𝑛n is divisible by 22;
  2. Replace 𝑛n with 2𝑛32n3 if 𝑛n is divisible by 33;
  3. Replace 𝑛n with 4𝑛54n5 if 𝑛n is divisible by 55.

For example, you can replace 3030 with 1515 using the first operation, with 2020 using the second operation or with 2424 using the third operation.

Your task is to find the minimum number of moves required to obtain 11 from 𝑛n or say that it is impossible to do it.

You have to answer 𝑞q independent queries.Input

The first line of the input contains one integer 𝑞q (1≤𝑞≤10001≤q≤1000) — the number of queries.

The next 𝑞q lines contain the queries. For each query you are given the integer number 𝑛n (1≤𝑛≤10181≤n≤1018).Output

Print the answer for each query on a new line. If it is impossible to obtain 11 from 𝑛n, print -1. Otherwise, print the minimum number of moves required to do it.
Exampleinput

7
1
10
25
30
14
27
1000000000000000000

output

0
4
6
6
-1
6
72

签到

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
ll n;
int main(){
	int T;cin>>T;
	while(T--){
		scanf("%lld",&n);
		int ans=0;
		while(n%5==0) n/=5,ans+=3;
		while(n%3==0) n/=3,ans+=2;
		while(n%2==0) n/=2,ans++;
		if(n>1) puts("-1");
		else printf("%d\n",ans);
	}
}


B. Merge it!

time limit per test1 second memory limit per test256 megabytes

You are given an array 𝑎a consisting of 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an.

In one operation you can choose two elements of the array and replace them with the element equal to their sum (it does not matter where you insert the new element). For example, from the array [2,1,4][2,1,4] you can obtain the following arrays: [3,4][3,4], [1,6][1,6] and [2,5][2,5].

Your task is to find the maximum possible number of elements divisible by 33 that are in the array after performing this operation an arbitrary (possibly, zero) number of times.

You have to answer 𝑡t independent queries.Input

The first line contains one integer 𝑡t (1≤𝑡≤10001≤t≤1000) — the number of queries.

The first line of each query contains one integer 𝑛n (1≤𝑛≤1001≤n≤100).

The second line of each query contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤1091≤ai≤109).Output

For each query print one integer in a single line — the maximum possible number of elements divisible by 33 that are in the array after performing described operation an arbitrary (possibly, zero) number of times.
Exampleinput

2
5
3 1 2 3 1
7
1 1 1 1 1 2 2

output

3
3

Note

In the first query of the example you can apply the following sequence of operations to obtain 33 elements divisible by 33: [3,1,2,3,1]→[3,3,3,1][3,1,2,3,1]→[3,3,3,1].

In the second query you can obtain 33 elements divisible by 33 with the following sequence of operations: [1,1,1,1,1,2,2]→[1,1,1,1,2,3]→[1,1,1,3,3]→[2,1,3,3]→[3,3,3][1,1,1,1,1,2,2]→[1,1,1,1,2,3]→[1,1,1,3,3]→[2,1,3,3]→[3,3,3].

水题,就是求个余数

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=(int)2e5+100;
int n;
int main(){
	int T;cin>>T;
	while(T--){
		scanf("%d",&n);
		int s[3]={0,};
		rep(i,1,n) {int a;scanf("%d",&a);s[a%3]++;}
		int ans=s[0];
		int t1=min(s[1],s[2]);
		ans+=t1;
		s[1]-=t1;s[2]-=t1;
		ans+=(s[1]+s[2])/3;
		printf("%d\n",ans);
	}
}


C. Lose it!

time limit per test2 seconds memory limit per test256 megabytes

You are given an array 𝑎a consisting of 𝑛n integers. Each 𝑎𝑖ai is one of the six following numbers: 4,8,15,16,23,424,8,15,16,23,42.

Your task is to remove the minimum number of elements to make this array good.

An array of length 𝑘k is called good if 𝑘k is divisible by 66 and it is possible to split it into 𝑘6k6 subsequences 4,8,15,16,23,424,8,15,16,23,42.

Examples of good arrays:

  • [4,8,15,16,23,42][4,8,15,16,23,42] (the whole array is a required sequence);
  • [4,8,4,15,16,8,23,15,16,42,23,42][4,8,4,15,16,8,23,15,16,42,23,42] (the first sequence is formed from first, second, fourth, fifth, seventh and tenth elements and the second one is formed from remaining elements);
  • [][] (the empty array is good).

Examples of bad arrays:

  • [4,8,15,16,42,23][4,8,15,16,42,23] (the order of elements should be exactly 4,8,15,16,23,424,8,15,16,23,42);
  • [4,8,15,16,23,42,4][4,8,15,16,23,42,4] (the length of the array is not divisible by 66);
  • [4,8,15,16,23,42,4,8,15,16,23,23][4,8,15,16,23,42,4,8,15,16,23,23] (the first sequence can be formed from first six elements but the remaining array cannot form the required sequence).

Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤5⋅1051≤n≤5⋅105) — the number of elements in 𝑎a.

The second line of the input contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (each 𝑎𝑖ai is one of the following numbers: 4,8,15,16,23,424,8,15,16,23,42), where 𝑎𝑖ai is the 𝑖i-th element of 𝑎a.Output

Print one integer — the minimum number of elements you have to remove to obtain a good array.
Examplesinput

5
4 8 15 16 23

output

5

input

12
4 8 4 15 16 8 23 15 16 42 23 42

output

0

input

15
4 8 4 8 15 16 8 16 23 15 16 4 42 23 42

output

3

南昌邀请赛原题,贪心求一下符合条件的数列有几个就好了

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
const int maxn=(int)5e5;
int n;
int t[11];
map<int,int> mp;
int main(){
	mp[4]=0;mp[8]=1;mp[15]=2;mp[16]=3;mp[23]=4;mp[42]=5;
	cin>>n;
	rep(i,1,n){
		int x; scanf("%d",&x); x=mp[x];
		if(x==0) t[0]++;
		else if(t[x]+1<=t[x-1]) t[x]++;
	}
	printf("%d\n",n-6*t[5]);
}


D. Recover it!

time limit per test4 seconds memory limit per test256 megabytes

Authors guessed an array 𝑎a consisting of 𝑛n integers; each integer is not less than 22 and not greater than 2⋅1052⋅105. You don’t know the array 𝑎a, but you know the array 𝑏b which is formed from it with the following sequence of operations:

  1. Firstly, let the array 𝑏b be equal to the array 𝑎a;
  2. Secondly, for each 𝑖i from 11 to 𝑛n:
    • if 𝑎𝑖ai is a prime number, then one integer 𝑝𝑎𝑖pai is appended to array 𝑏b, where 𝑝p is an infinite sequence of prime numbers (2,3,5,…2,3,5,…);
    • otherwise (if 𝑎𝑖ai is not a prime number), the greatest divisor of 𝑎𝑖ai which is not equal to 𝑎𝑖ai is appended to 𝑏b;
  3. Then the obtained array of length 2𝑛2n is shuffled and given to you in the input.

Here 𝑝𝑎𝑖pai means the 𝑎𝑖ai-th prime number. The first prime 𝑝1=2p1=2, the second one is 𝑝2=3p2=3, and so on.

Your task is to recover any suitable array 𝑎a that forms the given array 𝑏b. It is guaranteed that the answer exists (so the array 𝑏b is obtained from some suitable array 𝑎a). If there are multiple answers, you can print any.Input

The first line of the input contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of elements in 𝑎a.

The second line of the input contains 2𝑛2n integers 𝑏1,𝑏2,…,𝑏2𝑛b1,b2,…,b2n (2≤𝑏𝑖≤27501312≤bi≤2750131), where 𝑏𝑖bi is the 𝑖i-th element of 𝑏b. 27501312750131 is the 199999199999-th prime number.Output

In the only line of the output print 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (2≤𝑎𝑖≤2⋅1052≤ai≤2⋅105) in any order — the array 𝑎a from which the array 𝑏b can be obtained using the sequence of moves given in the problem statement. If there are multiple answers, you can print any.
Examplesinput

3
3 5 2 3 2 4

output

3 4 2 

input

1
2750131 199999

output

199999 

input

1
3 6

output

6 

依次扫过每个数,如果这个数是素数,那么则判断第ai个素数是否在数列中(很显然用线性筛预处理出来所有的素数)
那如果没找到或者不是素数那怎么办呢;
考虑到做素数筛的时候是可以处理出最大质因子的,而题目要求恰好也是最大出现除数,容易想到判断i/check[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
typedef long long ll;
const int maxn=(int)2e5+100;
const int maxp=(int)2750131;
int n,a[2*maxn];
int pos=1,prime[maxn];
int check[maxp+25],cnt[maxp+25];
vector<int> ans;
void f(){
	rep(i,2,maxp){
		if(!check[i]){
			for(int j=i*2;j<=maxp;j+=i) if(!check[j]) check[j]=i;
		}
	}
	rep(i,2,maxp) if(!check[i]) prime[pos++]=i;
}
int main(){
	f(); cin>>n;
	rep(i,1,n*2) scanf("%d",&a[i]),cnt[a[i]]++;
	dep(i,maxp,2){
		if(!cnt[i]) continue;
		while(cnt[i]--){
			if(!check[i]){
				int p=lower_bound(prime+1,prime+pos,i)-prime;
				if(cnt[p]) ans.pb(p),cnt[p]--;
			}
			else if(cnt[i/check[i]]) ans.pb(i),cnt[i/check[i]]--;
		}
	}
	for(auto it:ans) printf("%d ",it);
}


E. Cover it!

time limit per test2 seconds memory limit per test256 megabytes

You are given an undirected unweighted connected graph consisting of 𝑛n vertices and 𝑚m edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Your task is to choose at most ⌊𝑛2⌋⌊n2⌋ vertices in this graph so each unchosen vertex is adjacent (in other words, connected by an edge) to at least one of chosen vertices.

It is guaranteed that the answer exists. If there are multiple answers, you can print any.

You will be given multiple independent queries to answer.Input

The first line contains a single integer 𝑡t (1≤𝑡≤2⋅1051≤t≤2⋅105) — the number of queries.

Then 𝑡t queries follow.

The first line of each query contains two integers 𝑛n and 𝑚m (2≤𝑛≤2⋅1052≤n≤2⋅105, 𝑛−1≤𝑚≤𝑚𝑖𝑛(2⋅105,𝑛(𝑛−1)2)n−1≤m≤min(2⋅105,n(n−1)2)) — the number of vertices and the number of edges, respectively.

The following 𝑚m lines denote edges: edge 𝑖i is represented by a pair of integers 𝑣𝑖vi, 𝑢𝑖ui (1≤𝑣𝑖,𝑢𝑖≤𝑛1≤vi,ui≤n, 𝑢𝑖≠𝑣𝑖ui≠vi), which are the indices of vertices connected by the edge.

There are no self-loops or multiple edges in the given graph, i. e. for each pair (𝑣𝑖,𝑢𝑖vi,ui) there are no other pairs (𝑣𝑖,𝑢𝑖vi,ui) or (𝑢𝑖,𝑣𝑖ui,vi) in the list of edges, and for each pair (𝑣𝑖,𝑢𝑖vi,ui) the condition 𝑣𝑖≠𝑢𝑖vi≠ui is satisfied. It is guaranteed that the given graph is connected.

It is guaranteed that ∑𝑚≤2⋅105∑m≤2⋅105 over all queries.Output

For each query print two lines.

In the first line print 𝑘k (1≤⌊𝑛2⌋1≤⌊n2⌋) — the number of chosen vertices.

In the second line print 𝑘k distinct integers 𝑐1,𝑐2,…,𝑐𝑘c1,c2,…,ck in any order, where 𝑐𝑖ci is the index of the 𝑖i-th chosen vertex.

It is guaranteed that the answer exists. If there are multiple answers, you can print any.
Exampleinput

2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
6 8
2 5
5 4
4 3
4 1
1 3
2 3
2 6
5 6

output

2
1 3
3
4 3 6

Note

In the first query any vertex or any pair of vertices will suffice.

Note that you don’t have to minimize the number of chosen vertices. In the second query two vertices can be enough (vertices 22 and 44) but three is also ok.

保证有解并且是连通图,那么一次奇偶染色就好了,不懂为什么能放在E题

#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)4e5+100;
int n,m;
int cnt,head[maxn],vis[maxn];
vector<int> ans[2];
struct node{
	int v,next;
}g[maxn];
void add(int u,int v){
	g[cnt]={v,head[u]}; head[u]=cnt++;
}
void init(){
	rep(i,0,n) head[i]=-1,vis[i]=0;
	cnt=0;
	ans[0].clear();ans[1].clear();
}
void dfs(int x,int op){
	vis[x]=1;
	ans[op].pb(x);
	for(int i=head[x];i+1;i=g[i].next){
		int v=g[i].v;
		if(vis[v]) continue;
		dfs(v,op^1);
	}
}
int main(){
	int T;cin>>T;
	while(T--){
		scanf("%d%d",&n,&m); 
		init();
		rep(i,1,m){
			int u,v;scanf("%d%d",&u,&v);
			add(u,v);add(v,u);
		}
		dfs(1,1);
		if(ans[0].size()*2>n){
			printf("%d\n",(int)ans[1].size());
			for(auto u:ans[1]) printf("%d ",u);
			puts("");
		}
		else{
			printf("%d\n",(int)ans[0].size());
			for(auto u:ans[0]) printf("%d ",u);
			puts("");
		}
		
	}
}


F. Destroy it!

time limit per test2 seconds memory limit per test256 megabytes

You are playing a computer card game called Splay the Sire. Currently you are struggling to defeat the final boss of the game.

The boss battle consists of 𝑛n turns. During each turn, you will get several cards. Each card has two parameters: its cost 𝑐𝑖ci and damage 𝑑𝑖di. You may play some of your cards during each turn in some sequence (you choose the cards and the exact order they are played), as long as the total cost of the cards you play during the turn does not exceed 33. After playing some (possibly zero) cards, you end your turn, and all cards you didn’t play are discarded. Note that you can use each card at most once.

Your character has also found an artifact that boosts the damage of some of your actions: every 1010-th card you play deals double damage.

What is the maximum possible damage you can deal during 𝑛n turns?Input

The first line contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of turns.

Then 𝑛n blocks of input follow, the 𝑖i-th block representing the cards you get during the 𝑖i-th turn.

Each block begins with a line containing one integer 𝑘𝑖ki (1≤𝑘𝑖≤2⋅1051≤ki≤2⋅105) — the number of cards you get during 𝑖i-th turn. Then 𝑘𝑖ki lines follow, each containing two integers 𝑐𝑗cj and 𝑑𝑗dj (1≤𝑐𝑗≤31≤cj≤3, 1≤𝑑𝑗≤1091≤dj≤109) — the parameters of the corresponding card.

It is guaranteed that ∑𝑖=1𝑛𝑘𝑖≤2⋅105∑i=1nki≤2⋅105.Output

Print one integer — the maximum damage you may deal.
Exampleinput

5
3
1 6
1 7
1 5
2
1 4
1 3
3
1 10
3 5
2 3
3
1 15
2 4
1 10
1
1 100

output

263

Note

In the example test the best course of action is as follows:

During the first turn, play all three cards in any order and deal 1818 damage.

During the second turn, play both cards and deal 77 damage.

During the third turn, play the first and the third card and deal 1313 damage.

During the fourth turn, play the first and the third card and deal 2525 damage.

During the fifth turn, play the only card, which will deal double damage (200200).

显然,对于每一轮,有效的牌只有花费为1的伤害最大的三张+花费为2的伤害最大的一张+花费为3的伤害最大的一张,那么对于每一轮,有效的牌数就只有5张;

用dp[i][j]表示取完第i轮时,一共取走了x张牌的最大伤害,j=x%10;
dp2[i][0]表示当前这轮中,取走了i张牌时的最大伤害
dp2[i][1]表示当前这轮中,取走了i张牌,并且有一张牌翻倍时的最大伤害

显然dp2数组是可以用背包维护的,但是考虑到每一轮的物品数只有5,枚举一下全排列也很快;

那么显然,维护完dp2数组之后,dp数组的更新就只要枚举每一轮结束后累计打的牌的数量%10这10个状态就可以了。

#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 F first
#define S second
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=(int)2e5+100;
const ll INF=(ll)1e18;
int n;
vector<int> card[maxn][4];
ll dp[maxn][10],dp2[maxn][2];
void init(){
	rep(i,1,maxn-1) rep(j,0,9) dp[i][j]=-INF;
	dp[1][0]=0;
	cin>>n;
	rep(i,1,n){
		int t;scanf("%d",&t);
		rep(j,1,t){
			int c,d;scanf("%d%d",&c,&d);
			card[i][c].pb(d);  //第i轮花费为c的牌的伤害
		}
	}
	rep(i,1,n) rep(j,1,3){
		int lim=(j==1?3:1);  //花费为j的牌可以取几张
		sort(card[i][j].begin(),card[i][j].end());
		reverse(card[i][j].begin(),card[i][j].end());
		while(card[i][j].size()>lim) card[i][j].pop_back();
	}
}
void slove(){
	rep(i,1,n){
		rep(j,0,3) rep(k,0,1) dp2[j][k]=-INF;
		dp2[0][0]=0;
		vector<pii> cur;
		rep(c,1,3) for(auto d:card[i][j]) cur.pb({c,d});
		sort(cur.begin(),cur.end());
		do{
			int re=3,pos=0;
			ll tot=0,mx=0;
			for(auto x:cur){
				pos++;
				if(x.F>re) break;
				re-=x.F; tot+=x.S;
				mx=max(mx,(ll)x.S);
				dp2[pos][0]=max(dp2[pos][0],tot);//取走pos张牌时的最大伤害
				dp2[pos][1]=max(dp2[pos][1],tot+mx);//取走pos张牌,并且有一张牌翻倍的最大伤害
			}
		}while(next_permutation(cur.begin(),cur.end()));//枚举全排列
		rep(j,0,9) rep(k,0,3){
			int nxt=(j+k)%10;
			int fl=(j+k>=10?1:0);//这一轮是否可以翻倍
			dp[i+1][nxt]=max(dp[i+1][nxt],dp[i][j]+dp2[k][fl]);
		}
	}
	ll ans=0;
	rep(i,0,9) ans=max(ans,dp[n+1][i]);
	printf("%lld\n",ans);
}
int main(){
	init();
	slove();
}

 

发表评论,支持MarkDown语法