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:
- Replace ?n with ?2n2 if ?n is divisible by 22;
- Replace ?n with 2?32n3 if ?n is divisible by 33;
- 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:
- Firstly, let the array ?b be equal to the array ?a;
- 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;
- 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();
}
