#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
void test_case() {
mp.clear();
int n; cin >> n;
int cnt1 = 0;
for (int i = 0; i < n; i++) {
int x; cin >> x;
mp[x]++;
if (mp[x] == 1) cnt1++;
if (mp[x] == 2) cnt1--;
}
if (cnt1 > 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();
}
If there is a unique number in a, output YES. Otherwise, output NO.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tests;
cin >> tests;
while (tests--) {
int64_t n, k;
cin >> n >> k;
if (k < 2 * n) {
cout << (n - k % n) * (n - k % n) << '\n';
} else if (n == 1 || k % 2 == 0 || k - 2 * (n - 1) != 3) {
cout << 0 << '\n';
} else {
cout << 2 - (n == 2) << '\n';
}
}
}
If $$$k \leq 2n$$$,the optimal solution is to form array $$$a$$$ with $$$1$$$ and $$$2$$$. The answer is $$$c_1^ 2$$$.Any other construction will result in a num of $$$1$$$ greater than $$$c_1$$$, obviously not the optimal one.
For $$$k>2n+1$$$,the answer is always $$$0$$$.If $$$k$$$ is even,we can easily form array $$$a$$$ with $$$n$$$ even numbers.If $$$k$$$ is odd,we can set $$$a_1=5$$$ and form $$$a_2,...,a_n$$$ with $$$n-1$$$ even numbers.
For $$$k=2n+1$$$,if $$$n=2$$$,$$$a=[2,3]$$$ is optimal and the answer is $$$1$$$.Otherwise($$$n>2$$$),$$$a=[1,4,2,...,2]$$$ is optimal and the answer is $$$2$$$.
#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 $$$max(a_i) \leq \Sigma a_i$$$.
In this problem,the difference is that you can make $$$a_i:=a_i+26$$$ any number of times.First determine whether the original array has a solution, and then greedily increase the minimum value by $$$26$$$.It can be proven that adding the array up to two times can provide a solution.
#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;
}
Coming soon...
#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;
}