心态又崩了，状态好一点的话可以AK的，又表演了一次赛后1a，我好菜啊
A. Remainder
time limit per test1 second memory limit per test256 megabytes
You are given a huge decimal number consisting of ?n digits. It is guaranteed that this number has no leading zeros. Each digit of this number is either 0 or 1.
You may perform several (possibly zero) operations with this number. During each operation you are allowed to change any digit of your number; you may change 0 to 1 or 1 to 0. It is possible that after some operation you can obtain a number with leading zeroes, but it does not matter for this problem.
You are also given two integers 0≤?<?<?0≤y<x<n. Your task is to calculate the minimum number of operations you should perform to obtain the number that has remainder 10?10y modulo 10?10x. In other words, the obtained number should have remainder 10?10y when divided by 10?10x.Input
The first line of the input contains three integers ?,?,?n,x,y (0≤?<?<?≤2⋅1050≤y<x<n≤2⋅105) — the length of the number and the integers ?x and ?y, respectively.
The second line of the input contains one decimal number consisting of ?n digits, each digit of this number is either 0 or 1. It is guaranteed that the first digit of the number is 1.Output
Print one integer — the minimum number of operations you should perform to obtain the number having remainder 10?10y modulo 10?10x. In other words, the obtained number should have remainder 10?10y when divided by 10?10x.
Examplesinput
11 5 2 11010100101
output
1
input
11 5 1 11010100101
output
3
Note
In the first example the number will be 1101010010011010100100 after performing one operation. It has remainder 100100 modulo 100000100000.
In the second example the number will be 1101010001011010100010 after performing three operations. It has remainder 1010 modulo 100000100000.
题目挺唬人的，其实就是截取原串的最后y位，然后从后往前第x位是1，其他都是0，看看有几个不一样就好了
#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 INF=0x3f3f3f3f;
int a[maxn];
int main(){
int n,x,y;cin>>n>>x>>y;
string s;cin>>s;
int ans=0;
for(int i=n-1;i>=n-x;--i){
if(i==n-1-y){
if(s[i]=='0') ans++;
}
else{
if(s[i]=='1') ans++;
}
}
printf("%d\n",ans);
}
B. Polycarp Training
time limit per test2 seconds memory limit per test256 megabytes
Polycarp wants to train before another programming competition. During the first day of his training he should solve exactly 11 problem, during the second day — exactly 22 problems, during the third day — exactly 33 problems, and so on. During the ?k-th day he should solve ?k problems.
Polycarp has a list of ?n contests, the ?i-th contest consists of ??ai problems. During each day Polycarp has to choose exactly one of the contests he didn't solve yet and solve it. He solves exactly ?k problems from this contest. Other problems are discarded from it. If there are no contests consisting of at least ?k problems that Polycarp didn't solve yet during the ?k-th day, then Polycarp stops his training.
How many days Polycarp can train if he chooses the contests optimally?Input
The first line of the input contains one integer ?n (1≤?≤2⋅1051≤n≤2⋅105) — the number of contests.
The second line of the input contains ?n integers ?1,?2,…,??a1,a2,…,an (1≤??≤2⋅1051≤ai≤2⋅105) — the number of problems in the ?i-th contest.Output
Print one integer — the maximum number of days Polycarp can train if he chooses the contests optimally.
Examplesinput
4 3 1 4 1
output
3
input
3 1 1 1
output
1
input
5 1 1 1 2 2
output
2
签到
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(int)2e5+100;
int a[maxn];
int main(){
int n;
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]); sort(a+1,a+1+n);
int k=1;
rep(i,1,n) if(a[i]>=k) k++;
printf("%d\n",k-1);
}
C. Good String
time limit per test1 second memory limit per test256 megabytes
Let's call (yet again) a string good if its length is even, and every character in odd position of this string is different from the next character (the first character is different from the second, the third is different from the fourth, and so on). For example, the strings good, stringand xyyx are good strings, and the strings bad, aa and aabc are not good. Note that the empty string is considered good.
You are given a string ?s, you have to delete minimum number of characters from this string so that it becomes good.Input
The first line contains one integer ?n (1≤?≤2⋅1051≤n≤2⋅105) — the number of characters in ?s.
The second line contains the string ?s, consisting of exactly ?n lowercase Latin letters.Output
In the first line, print one integer ?k (0≤?≤?0≤k≤n) — the minimum number of characters you have to delete from ?s to make it good.
In the second line, print the resulting string ?s. If it is empty, you may leave the second line blank, or not print it at all.
Examplesinput
4 good
output
0 good
input
4 aabc
output
2 ab
input
3 aaa
output
3
删除字符的策略是，当前字符和下一个一样的话把当前的删掉，记录删除字符的总数，如果和原串的奇偶性不相同则再删掉最后一个字符
#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 INF=0x3f3f3f3f;
int main(){
int n;cin>>n;
string s;cin>>s;
int tot=0;
for(int i=0;i+1<n;i+=2) if(s[i]==s[i+1]) s[i]='#',i--,tot++;
if((n%2==0&&tot%2)||(n%2&&tot%2==0)) s[n-1]='#',tot++;
printf("%d\n",tot);
for(int i=0;i<n;++i) if(s[i]!='#') cout<<s[i];
}
D. Almost All Divisors
time limit per test2 seconds memory limit per test256 megabytes
We guessed some integer number ?x. You are given a list of almost all its divisors. Almost all means that there are all divisors except 11and ?x in the list.
Your task is to find the minimum possible integer ?x that can be the guessed number, or say that the input data is contradictory and it is impossible to find such number.
You have to answer ?t independent queries.Input
The first line of the input contains one integer ?t (1≤?≤251≤t≤25) — the number of queries. Then ?t queries follow.
The first line of the query contains one integer ?n (1≤?≤3001≤n≤300) — the number of divisors in the list.
The second line of the query contains ?n integers ?1,?2,…,??d1,d2,…,dn (2≤??≤1062≤di≤106), where ??di is the ?i-th divisor of the guessed number. It is guaranteed that all values ??di are distinct.Output
For each query print the answer to it.
If the input data in the query is contradictory and it is impossible to find such number ?x that the given list of divisors is the list of almost all its divisors, print -1. Otherwise print the minimum possible ?x.
Exampleinput
2 8 8 2 12 6 4 24 16 3 1 2
output
48 4
很容易想到，假设序列是合法的，那么给原数列排个序，a[1]*a[n]=a[2]*a[n-1]=a[3]*a[n-2]=....=ans对于所有i都成立
这样判断完之后再看看我们得到的ans分解出来的因数个数和题目给的一不一样
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll 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 INF=0x3f3f3f3f;
ll a[330];
int main(){
int T;cin>>T;
while(T--){
int n;cin>>n;
rep(i,1,n) scanf("%lld",&a[i]); sort(a+1,a+1+n);
ll ans=a[1]*a[n];
int flag=0;
rep(i,2,(n+1)/2){
if(a[i]*a[n-i+1]!=ans){flag=1;break;}
}
int num=0;
rep(i,2,sqrt(ans)){
if(ans%i==0){
if(i*i==ans) num++;
else num+=2;
}
}
if(num!=n) flag=1;
if(flag) puts("-1");
else printf("%lld\n",ans);
}
}
E. Two Arrays and Sum of Functions
time limit per test2 seconds memory limit per test256 megabytes
You are given two arrays ?a and ?b, both of length ?n.
Let's define a function ?(?,?)=∑?≤?≤???⋅??f(l,r)=∑l≤i≤rai⋅bi.
Your task is to reorder the elements (choose an arbitrary order of elements) of the array ?b to minimize the value of ∑1≤?≤?≤??(?,?)∑1≤l≤r≤nf(l,r). Since the answer can be very large, you have to print it modulo 998244353998244353. Note that you should minimize the answer but not its remainder.Input
The first line of the input contains one integer ?n (1≤?≤2⋅1051≤n≤2⋅105) — the number of elements in ?a and ?b.
The second line of the input contains ?n integers ?1,?2,…,??a1,a2,…,an (1≤??≤1061≤ai≤106), where ??ai is the ?i-th element of ?a.
The third line of the input contains ?n integers ?1,?2,…,??b1,b2,…,bn (1≤??≤1061≤bj≤106), where ??bj is the ?j-th element of ?b.Output
Print one integer — the minimum possible value of ∑1≤?≤?≤??(?,?)∑1≤l≤r≤nf(l,r) after rearranging elements of ?b, taken modulo 998244353998244353. Note that you should minimize the answer but not its remainder.
Examplesinput
5 1 8 7 2 4 9 7 2 9 3
output
646
input
1 1000000 1000000
output
757402647
input
2 1 3 4 2
output
20
因为a不能换位置，所以对于每个a[i]，它对于答案的贡献次数就是 (n-i+1)*i ；
又由于b是可以换位置的，那么将a乘上贡献次数的权值之后降序排列，再把b升序排列，两两相乘得到的结果必然最小(反证法证明)
#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 INF=0x3f3f3f3f;
const int mod=998244353;
ll a[maxn],b[maxn],n;
int main(){
cin>>n;
for(ll i=1;i<=n;++i){
scanf("%lld",&a[i]);
a[i]*=((n-i+1)*i);
}
rep(i,1,n) scanf("%lld",&b[i]);
sort(b+1,b+1+n,greater<int>());
sort(a+1,a+1+n);
ll ans=0;
rep(i,1,n){
ans+=((a[i]%mod)*(b[i]%mod))%mod;
}
ans=(ans+mod)%mod;
printf("%lld\n",ans);
}
F2. Microtransactions (hard version)
time limit per test3 seconds memory limit per test256 megabytes
The only difference between easy and hard versions is constraints.
Ivan plays a computer game that contains some microtransactions to make characters look cooler. Since Ivan wants his character to be really cool, he wants to use some of these microtransactions — and he won't start playing until he gets all of them.
Each day (during the morning) Ivan earns exactly one burle.
There are ?n types of microtransactions in the game. Each microtransaction costs 22 burles usually and 11 burle if it is on sale. Ivan has to order exactly ??ki microtransactions of the ?i-th type (he orders microtransactions during the evening).
Ivan can order any (possibly zero) number of microtransactions of any types during any day (of course, if he has enough money to do it). If the microtransaction he wants to order is on sale then he can buy it for 11 burle and otherwise he can buy it for 22 burles.
There are also ?m special offers in the game shop. The ?j-th offer (??,??)(dj,tj) means that microtransactions of the ??tj-th type are on sale during the ??dj-th day.
Ivan wants to order all microtransactions as soon as possible. Your task is to calculate the minimum day when he can buy all microtransactions he want and actually start playing.Input
The first line of the input contains two integers ?n and ?m (1≤?,?≤2⋅1051≤n,m≤2⋅105) — the number of types of microtransactions and the number of special offers in the game shop.
The second line of the input contains ?n integers ?1,?2,…,??k1,k2,…,kn (0≤??≤2⋅1050≤ki≤2⋅105), where ??ki is the number of copies of microtransaction of the ?i-th type Ivan has to order. It is guaranteed that sum of all ??ki is not less than 11 and not greater than 2⋅1052⋅105.
The next ?m lines contain special offers. The ?j-th of these lines contains the ?j-th special offer. It is given as a pair of integers (??,??)(dj,tj) (1≤??≤2⋅105,1≤??≤?1≤dj≤2⋅105,1≤tj≤n) and means that microtransactions of the ??tj-th type are on sale during the ??dj-th day.Output
Print one integer — the minimum day when Ivan can order all microtransactions he wants and actually start playing.
Examplesinput
5 6 1 2 0 2 0 2 4 3 3 1 5 1 2 1 5 2 3
output
8
input
5 3 4 2 1 3 2 3 5 4 2 2 5
output
20
显然可以二分答案，那么难点就在于如何判断这个答案的合理性
我们贪心的去想，最坏情况下需要sum*2天，所以只有用到了优惠才能减小答案，也就是说优惠的商品数量越多越好
所以显然，如果同一个商品在不同几天都有优惠政策，肯定是最后一天用情况更优，因为我需要用到更多的优惠次数，如果之前有优惠就用掉了，可能会有后面的优惠钱不够的情况
#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;
const int INF=0x3f3f3f3f;
int n,m,sum=0,M;
int a[maxn];
vector<int> v[maxn];
int ck(int x){
int last[maxn]={0,},tem[maxn]={0,},mon=0,tot=0;
rep(i,1,x) for(auto j:v[i]) last[j]=max(last[j],i);
rep(i,1,x){
++mon;
for(auto j:v[i])
while(tem[j]<a[j]&&mon&&last[j]==i) --mon,tem[j]++,tot++;
}
return mon>=(sum-tot)*2;
}
int main(){
cin>>n>>m;
rep(i,1,n) scanf("%d",&a[i]),sum+=a[i];
rep(i,1,m){
int d,t;scanf("%d%d",&d,&t);M=max(M,d);
v[d].pb(t);
}
int l=0,r=sum*2,m=(l+r)>>1,ans=0;
while(l<=r){
if(ck(m)) ans=m,r=m-1;
else l=m+1;
m=(l+r)>>1;
}
printf("%d\n",ans);
}
