#include <bits/stdc++.h>
using namespace std;
void test_case() {
int a, b, c, n; cin >> a >> b >> c >> n;
c = min(c, n / 100); n -= c * 100;
b = min(b, n / 10); n -= b * 10;
a = min(a, n); n -= a;
if (n == 0) cout << "YES\n";
else cout << "NO\n";
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) test_case();
}
We only need to use $100 coins as much as possible first, then $10 coins as much as possible, and finally $1 coins.
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int T; cin >> T;
while(T--) {
int n; cin >> n;
vector<int> a(n), b(n);
long long ans = LLONG_MIN, sum = 0, sa = 0, sb = 0;
for(auto &i: a) cin >> i;
for(auto &i: b) cin >> i, sum += i;
ans = 2 * a.back() - sum;
for(int i = n - 1 ; i >= 0 ; i--) {
sa += a[i], sb += b[i];
ans = max(ans, min((sa - a.back()) - (sb - b[i]), sa - (sum - b.back())));
}
cout << ans << '\n';
}
return 0;
}
Consider enumerate $$$i_a$$$ from $$$1$$$ to $$$n$$$.
For a fixed $$$i_a$$$,Bob has only two possible optimal options:choose $$$i_b=1 or i_a+1(if i_a \neq n)$$$.So Bob chooses $$$min(a_{i_a}+...+a_n-(b_1+...+b_{n-1}),a_{i_a}+...+a_{n-1}-(b_{i_a+1}+...+b_n))$$$.
Note $$$score_i$$$ as the answer for fixed $$$i_a=i$$$,the final answer is $$$max(score_i)$$$.
#include <bits/stdc++.h>
using namespace std;
#define N 210000
string s;
void test_case() {
int n; cin >> n >> s;
sort(begin(s), end(s));
int sum = 0;
for (int i = 0; i < n; i++)
sum += s[i] - 'a';
if (sum % 2 != 0) {cout << -1 << '\n'; return;}
int ans = n * 100;
if (s[n - 1] - 'a' <= sum - s[n - 1] + 'a')
ans = sum;
for (int i = 0; i < n; i++) {
int sumcur = sum - s[i] + 'a';
int valcur = s[i] - 'a' + 26;
int num = (max(0, valcur - sumcur) + 25) / 26;
if (num > i) continue;
ans = min(ans, sum + 26 + num * 26);
}
if (ans == n * 100) {cout << -1 << '\n'; return;}
cout << ans / 2 << '\n';
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) test_case();
}
For $$$n=2$$$,if $$$s_1 \neq s_2$$$ ,output $$$-1$$$.Otherwise,output $$$s_1-'a'$$$.
For $$$n>2$$$,let's consider a classic problem:for a given array $$$a$$$,you can make $$$a_i--,a_j--$$$,determine if you can make all numbers to $$$0$$$.
Check if $$$2max(a_i) \leq \Sigma a_i$$$.If $$$2max(a_i) \leq \Sigma a_i$$$ we can make all numbers to $$$0$$$.Otherwise we can't.
Let's go back to this problem.Let's see string $$$s$$$ as the array $$$a$$$ above.Note $$$opr_i$$$ as the number of times we operate on $$$s_i$$$.We can get $$$opr_i=(a_i-'a')+26k_i$$$ since we want all $$$a_i='a'$$$.Now our task is minimize $$$\Sigma k_i$$$.
First check if the original array satisfies $$$2max(a_i) \leq \Sigma a_i$$$.If not,then greedily increase the minimum value by $$$26$$$.It can be proven that we can get $$$2max(a_i) \leq \Sigma a_i$$$ after adding the array at most two times .
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=4010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int n,q;
int a[N*N];
int S[N][N];
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n*n;i++)
{
scanf("%d",&a[i]);
S[i%(2*n)][(i+2*n)/(2*n)]=S[i%(2*n)][(i+2*n)/(2*n)-1]+a[i];
}
for(int i=1;i<=q;i++)
{
int t,x,p1,p2,ans=0;
scanf("%d%d",&t,&x);
p1=t-x+1;p2=t-2*n+x;
if(p1>0) ans+=S[p1%(2*n)][(p1+2*n)/(2*n)];
if(p2>0) ans+=S[p2%(2*n)][(p2+2*n)/(2*n)];
printf("%d\n",ans);
}
return 0;
}
The key to solving the problem lies in observing:If we group all elements in $$$a$$$ according to the index mod $$$2n$$$, then at all times, the elements of the same group will always be in the same column.
We divide the elements in $$$a$$$ into $$$2n$$$ groups and build prefix sum arrays for each group. For each query, we calculate which two groups pass through this column, and then calculate the answer with the two prefix sum arrays.
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n;
ll sum;
int p[N],pos[N],sig[N],BIT[N];
void add(int p,int v)
{
for(int i=p;i<=n;i+=(i&-i)) BIT[i]+=v;
}
int getsum(int p)
{
int s=0;
for(int i=p;i;i-=(i&-i)) s+=BIT[i];
return s;
}
struct nod
{
int l,r,sum,tag;
nod *lc,*rc;
};
struct Segtree
{
nod *root;
Segtree()
{
build(&root,1,n);
}
void newnod(nod **p,int L,int R)
{
*p=new nod;
(*p)->l=L;(*p)->r=R;(*p)->sum=1;(*p)->tag=0;
}
void build(nod **p,int L,int R)
{
newnod(p,L,R);
if(L==R) return ;
int M=(L+R)>>1;
build(&(*p)->lc,L,M);
build(&(*p)->rc,M+1,R);
(*p)->sum=(*p)->lc->sum+(*p)->rc->sum;
}
void pushdown(nod *p)
{
if(p->tag) p->sum*=-1;
if(p->l!=p->r)
{
p->lc->tag^=p->tag;
p->rc->tag^=p->tag;
}
p->tag=0;
}
void flip(int L,int R)
{
_flip(root,L,R);
}
void _flip(nod *p,int L,int R)
{
pushdown(p);
if(p->l==L&&p->r==R)
{
p->tag^=1;
return ;
}
int M=(p->l+p->r)>>1;
if(R<=M) _flip(p->lc,L,R);
else if(L>M) _flip(p->rc,L,R);
else _flip(p->lc,L,M),_flip(p->rc,M+1,R);
pushdown(p->lc);pushdown(p->rc);
p->sum=p->lc->sum+p->rc->sum;
}
int getsum(int L,int R)
{
return _getsum(root,L,R);
}
int _getsum(nod *p,int L,int R)
{
pushdown(p);
if(p->l==L&&p->r==R) return p->sum;
int M=(p->l+p->r)>>1;
if(R<=M) return _getsum(p->lc,L,R);
else if(L>M) return _getsum(p->rc,L,R);
else return _getsum(p->lc,L,M)+_getsum(p->rc,M+1,R);
}
};
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&p[i]),pos[p[i]]=i;
Segtree TR;
sum=0;
for(int i=1;i<=n;i++) BIT[i]=0;
for(int i=1;i<=n;i++)
{
sig[i]=(getsum(p[i])&1)?-1:1;
add(p[i],1);
}
for(int i=1;i<=n;i++)
{
sum+=((pos[i]&1)?1:-1)*(ll)(pos[i]-1)*i;
sum+=(ll)(sig[pos[i]]*TR.getsum(pos[i],pos[i])*TR.getsum(pos[i],n))*i;
TR.flip(pos[i],n);
}
printf("%I64d\n",sum);
}
return 0;
}
Consider calculating the contribution of each element separately.
For an element,we can observe that only elements with values less than it and indexes greater than it increase its index by $$$1$$$.
We represent these 'influence' as a sequence $$$s$$$ containing only $$$1$$$ and $$$-1$$$.At the beginning,$$$s_i=1$$$ for all $$$1\leq i \leq n$$$.We calculate the contribution of each element in ascending order of values.
Assuming we have already calculated the contribution of $$$x$$$,then we do filp $$$s_{pos_x},...,s_n$$$ (flip denotes making $$$1$$$ to $$$-1$$$ and make $$$-1$$$ to $$$1$$$) and calculate the contribution of $$$x+1$$$ using updated $$$s$$$.
#include <bits/stdc++.h>
// v.erase( unique(all(v)) , v.end() ) -----> removes duplicates and resizes the vector as so
using namespace std;
#define IO_file freopen("output.txt","w",stdout), freopen("input.txt","r",stdin);
#define ll long long
#define lld long double
const lld pi = 3.14159265358979323846;
#define pb push_back
#define pf push_front
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
constexpr int mod = (int)(1e9 + 7);
#define log(x) (31^__builtin_clz(x)) // Easily calculate log2 on GNU G++ compilers
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int x, int y) {
return uniform_int_distribution<int>(x, y)(rng);
}
struct AhoCorasick {
//The trie
struct tr_node {
int adj[26];
int link;
int parent;
int term;
tr_node() {
link = 0;
parent = -1;
term = 0;
memset(adj, -1, sizeof(adj));
}
};
vector<tr_node> tr;
int tick = 0;//--> tick is the number of nodes in the trie
AhoCorasick() {
init();
}
void init() {
tr.clear();
tr.push_back(tr_node());
tick = 0;
tr[0].link = -1;
}
void insert(const string &s) {
int p = 0;
for(int i=0;i<s.size();i++){
if(tr[p].adj[s[i]-'a'] == -1){
tr.push_back(tr_node());
tr[p].adj[s[i]-'a'] = (++tick);
}
p = tr[p].adj[s[i]-'a'];
}
tr[p].term++;
}
//build the suffix links and transitions for each node
//in Amortized O(sizeof the strings inserted in the trie + No.nodes*sizeofAlphabet).
//this implementation has less memory usage, so you choose which to run.
//you can add an additional array "adj" to build a tree over the suffix links.
vector<int> character;
//we build the suffix links only and we calculate transitions on the run
int trans(int p, int c) {
//p is the node, c is the character
while(p != -1 && tr[p].adj[c] == -1) p = tr[p].link;
if(p == -1) return 0;//we return the root
return tr[p].adj[c];
}
void build() {
character.resize(tick+5);
queue<int> q; q.push(0);
character[0] = -1;
while(!q.empty()){
int p = q.front(); q.pop();
if(p){
if(tr[tr[p].parent].link != -1){
tr[p].link = trans(tr[tr[p].parent].link, character[p]);
}
if(tr[p].link != -1){
tr[p].term += tr[tr[p].link].term;
}
}
for(int i = 0 ; i < 26 ; i++){
if(tr[p].adj[i] != -1){
tr[tr[p].adj[i]].parent = p;
character[tr[p].adj[i]] = i;
q.push(tr[p].adj[i]);
continue;
}
}
}
}
}Aho[20];
vector<string> info[20];
void add(const string &s) {
for(int i = 0 ; i < 20 ; i++){
if(info[i].size() == 0){
for(int j = 0 ; j < i ; j++){
for(string x : info[j]){
info[i].pb(x);
}
vector<string> v;
info[j].swap(v);
Aho[j].init();
}
info[i].pb(s);
for(string x : info[i]){
Aho[i].insert(x);
}
Aho[i].build();
break;
}
}
}
ll query(const string &s) {
ll cnt = 0;
for(int i = 0 ; i < 20 ; i++){
if(info[i].empty()) continue;
int p = 0;
for(int j = 0 ; j < s.size() ; j++){
p = Aho[i].trans(p, s[j] - 'a');
cnt += Aho[i].tr[p].term;
}
}
return cnt;
}
const int N = 2e5 + 7;
const int M = 4e5 + 7;
int n, par[M], fake_node;
vector<int> adj[M];
string str[N];
string qry_str[N];
void init() {
for(int i = 0 ; i <= 2 * n ; i++){
par[i] = i;
}
fake_node = n;
}
int find(int x) {
if(x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if(x == y) return;
fake_node++;
par[x] = fake_node;
par[y] = fake_node;
adj[fake_node].pb(x);
adj[fake_node].pb(y);
}
int in[M], out[M], tick, node_at[M];
void dfs(int node) {
in[node] = ++tick;
node_at[tick] = node;
for(int u : adj[node]){
dfs(u);
}
out[node] = tick;
}
vector<pair<int, bool > > queries2[M]; // the query indx, 0 pos | 1 neg
int main()
{ios_base::sync_with_stdio(0),cin.tie(0);
cin>>n;
init();
for(int i = 1 ; i <= n ; i++){
cin>>str[i];
}
int q; cin>>q;
vector<pair<int, int> > queries; // the node, the query indx
vector<int> quests;
for(int i = 0 ; i < q ; i++){
int t; cin>>t;
if(t == 1){
int a, b; cin>>a>>b;
merge(a, b);
continue;
}
int v; cin>>v;
cin>>qry_str[i];
v = find(v);
queries.pb({v, i});
quests.pb(i);
}
for(int i = 1 ; i < n ; i++){
merge(i, i + 1);
}
int root = find(1);
dfs(root);
for(pair<int, int> X : queries){
int v = X.first; int indx = X.second;
queries2[out[v]].pb({indx, 0});
if(v != root){
queries2[in[v] - 1].pb({indx, 1});
}
}
ll ans[q] = {};
for(int i = 1 ; i <= tick ; i++){
int u = node_at[i];
if(u <= n){
add(str[u]);
}
for(pair<int, int> X : queries2[i]){
int indx = X.first;
bool o = X.second;
if(o){
ans[indx] -= query(qry_str[indx]);
}
else {
ans[indx] += query(qry_str[indx]);
}
}
}
for(int i = 0 ; i < quests.size() ; i++){
cout<<ans[quests[i]]<<'\n';
}
return 0;
}
We will answer the queries offline.
We will use DSU to process queries of the first type.
For each query of the first type, we will create a new node $$$H$$$ and connect both $$$u$$$ and $$$v$$$ to it.
For each query of the second type, we will add the query to the query-list of the root of the component $$$u$$$ is in.
Now we merge all the components together and we notice that now we have a tree and each query of the second type turns out to be a subtree query in our tree.
We run euler tour on the tree and now each subtree query is a range query in the euler tour array, for example it's a query on $$$[L, R]$$$, the answer to it is the answer on $$$[1, R]$$$ minus the answer on $$$[1, L - 1]$$$.
to answer these prefix queries we will use dynamic Aho-Corasick to add the strings and answer the queries.
The amortized time complexity of this solution is $$$O(N * log(N) * AlphabetSize)$$$.
