Codeforces Round 988 (Div. 3) Summary
A
There's not much to say. Use a bucket to store the number of occurrences.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=25;
int n;
int a[N],c[N];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],c[a[i]]++;
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=c[i]/2;
c[i]=0;
}
cout<<ans<<'\n';
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
B
Based on the meaning of the question, we have\(n \times m+2=k\)follow\(n \times m=k-2\)will\(k-2\) Decomposition, checking whether the presence of\(a\) The center will be fine.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int k;
int a[N],c[N];
void solve()
{
cin>>k;
for(int i=1;i<=k;i++) cin>>a[i],c[i]=0;
for(int i=1;i<=k;i++) c[a[i]]++;
int x=k-2;
for(int i=1;1ll*i*i<=x;i++)
if(x%i==0&&c[i]&&c[x/i])
{
cout<<i<<' '<<x/i<<'\n';
return ;
}
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
C
It is easy to think, first of all, that it is feasible to add odd numbers together, even numbers together, and the smallest odd combination is\(9=4+5\)So.\(n \ge 5\) There is a solution.\(n=5\) this time\(1,3,5,4,2\)。\(n>5\) Simply add even numbers to the end of the queue and odd numbers to the head of the queue.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
int a[N];
void solve()
{
cin>>n;
if(n<=4)
{
cout<<-1<<'\n';
return ;
}
int cnt=0;
for(int i=7;i<=n;i+=2) cout<<i<<' ';
cout<<"1 3 5 4 2 ";
for(int i=6;i<=n;i+=2) cout<<i<<' ';
cout<<'\n';
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
D
Consider greed, first of all can not pick up not pick up, encounter obstacles can not jump over, only to return to pick up the gas pedal, the requirement to pick up the smallest number of times, so go back to pick up the gas pedal to pick up the first big.
Thus enumerating the obstacles\(i\)To jump over, you have to fulfill\(k \ge r_i-l_i+2\), use the big root heap to store the information of the gas pedal, if all of them are taken out and added to the\(k\) on is still not satisfied, indicating that it cannot be completed.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,L;
int l[N],r[N];
int x[N],v[N];
priority_queue<int> q;
void solve()
{
cin>>n>>m>>L;
for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
for(int i=1;i<=m;i++) cin>>x[i]>>v[i];
int k=1,id=1,ans=0;
for(int i=1;i<=n;i++)
{
int len=r[i]-l[i]+2;
while(x[id]<l[i]&&id<=m) (v[id]),id++;
while(()&&k<len) k+=(),ans++,();
if(k<len)
{
cout<<-1<<'\n';
return ;
}
}
while(()) ();
cout<<ans<<'\n';
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
E
Interactive questions, remember to useendl or() Empty the cache.
The maximum number of queries is\(n\)set up\(k_i=f(1,i)\) \((2 \le i \le n)\)。
Consider first the unsolved case, which is clearly\(k_n=0\) The answer cannot be determined at the time.
And then iterating through the\(k\), consider what would happen if\(s_i=0\)then there must be\(k_i=k_{i-1}\). So when\(k_i>k{i-1}\) when\(s_i=1\). But this has a problem if\(s\) because of\(\mathtt{111\dots000\dots1\dots}\)Then the beginning of the\(1\) Neither will contribute. So finding the first one is not the same as\(0\) (used form a nominal expression)\(k_i\)Description\([1,i-1]\) there are\(k_i\) classifier for individual things or people, general, catch-all classifier\(0\)So the beginning of the\(i-1-k_i\) classifier for individual things or people, general, catch-all classifier\(1\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=1e4+5;
int n;
int s[N];
int query(int l,int r)
{
int x;
cout<<"? "<<l<<" "<<r<<' '<<endl;
cin>>x;
return x;
}
int k[N];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) s[i]=0;
for(int i=2;i<=n;i++) k[i]=query(1,i);
if(k[n]==0)
{
cout<<"! IMPOSSIBLE "<<endl;
return ;
}
for(int i=2;i<=n;i++) if(k[i]>k[i-1]) s[i]=1;
for(int i=2;i<=n;i++)
if(s[i])
{
for(int j=1;j<=i-1-k[i];j++) s[j]=1;
break;
}
cout<<"! ";
for(int i=1;i<=n;i++) cout<<s[i];
cout<<' '<<endl;
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
F
Two-point answer. Set up an attack.\(k\) Times.
Because it can only be in the same position\(p\) attack, so the first\(i\) Each enemy needs to take at least\(t_i=\lceil\frac{h_i}{k}\rceil\) of the injury, and therefore\(p\) The scope of the\([x_i-(m-t[i]),x_i+(m-t[i])]\)if\(m < t_i\) Then it must not be possible to defeat the first\(i\) An enemy.
This translates into\(n\) The coverage problem for intervals asks whether a point is covered at least\(k\) Times.
Discretization plus differencing is easy with a complexity of\(O(n\log(n)\log(V))\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=2e5+5,inf=1e9;
int n,m,k;
int h[N],x[N],t[N];
int tot;
int b[N],c[N];
bool check(int k)
{
tot=0;
for(int i=1;i<=n;i++)
{
t[i]=(h[i]+k-1)/k;
if(t[i]<=m)
{
c[++tot]=x[i]-(m-t[i]);
c[++tot]=x[i]+(m-t[i])+1;
}
}
sort(c+1,c+tot+1);
tot=unique(c+1,c+tot+1)-c-1;
for(int i=1;i<=tot;i++) b[i]=0;
for(int i=1;i<=n;i++)
{
if(t[i]<=m)
{
int l=lower_bound(c+1,c+tot+1,x[i]-(m-t[i]))-c;
int r=lower_bound(c+1,c+tot+1,x[i]+(m-t[i])+1)-c;
b[l]++,b[r]--;
}
}
for(int i=1;i<=tot;i++) b[i]+=b[i-1];
for(int i=1;i<=tot;i++) if(b[i]>=k) return 1;
return 0;
}
void solve()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>h[i];
for(int i=1;i<=n;i++) cin>>x[i];
int l=1,r=inf,mid,ans=-1;
while(l<=r)
{
mid=l+r>>1;
if(check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
cout<<ans<<'\n';
}
int main ()
{
#ifndef ONLINE_JUDGE
freopen("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
G
dp plus tolerant repulsion.
Deriving step by step, set\(f_i\) ex-\(1\) until (a time)\(i\) The number of scenarios that are simulated as per the question is there:
Doing so is\(O(n^2)\) The.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=998244353,M=1e6+5;
int n;
int a[N];
int f[N];
int gcd(int x,int y)
{
return y ? gcd(y,x%y) : x;
}
vector<int> g[M],h[N];
set<int> v;
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
f[1]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=i-1;j++)
if(gcd(a[i],a[j])!=1)
f[i]=(f[i]+f[j])%mod;
cout<<f[n]<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
solve();
return 0;
}
Considering optimization, it's easy to see that we don't really care about specific\(\gcd(a_i,a_j)\) What is it? Just ask for nothing.\(1\)will\(a_i\) prime factorization.\(a_i\) together with\(a_j\) is linked by the same prime factors. Each time the decomposition of\(a_i\), looking for a front position to shift.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=998244353,M=1e6+5;
int n;
int a[N],f[N];
vector<int> g[M],h[N];
set<int> v;
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int x=a[1];
for(int j=2;1ll*j*j<=n;j++)
{
if(x%j==0)
{
g[j].push_back(1);
while(x%j==0) x/=j;
}
}
if(x>1) g[x].push_back(1);
f[1]=1;
for(int i=2;i<=n;i++)
{
int x=a[i];
for(int j=2;1ll*j*j<=x;j++)
{
if(x%j==0)
{
for(int k:g[j])
{
if((k)==0) f[i]=(f[i]+f[k])%mod;
(k);
}
g[j].push_back(i);
while(x%j==0) x/=j;
}
}
if(x>1)
{
for(int k:g[x])
{
if((k)==0) f[i]=(f[i]+f[k])%mod;
(k);
}
g[x].push_back(i);
}
();
}
cout<<f[n]<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
solve();
return 0;
}
But that still doesn't pass. Because it's still at worst\(O(n^2)\) The, casually jammed off.
It may then be useful to divide the set by prime factors, setting\(b_x\) is a prime factor of\(x\) of the number of contributions generated. In this way each time\(a_i\) break down\(x\) \(f_i\) Just add\(b_x\) That's fine. But you can't even pass the sample if you just do that.
Consider this set of data\(\mathtt{6,6}\)。\(i=1\)，\(f_1=1\)Updates\(b\)Yes\(b_2=1,b_3=1\)。\(i=2\)，\(f_2=b_2+b_3=2\)But it's actually\(f_2=1\)。
Here it is.\(2\) cap (a poem)\(3\) Double-counting, since there's obviously a subtraction to be made here\(6\) Number of occurrences\(1\)。
How can we avoid such a situation? Use the principle of tolerant repulsion.
commander-in-chief (military)\(a_i\) After the prime factorization, each prime factorFetch only onceMultiply to get\(y\)abstraction\(y\) are placed in the dynamic arrayg[a[i]] center. For exampleg[12]={2,3,6}，g[6]={2,3,6}, at which point the above example can be calculated.\(i=1\)Yes\(b_2=b_3=b_6=1\)，\(i=2\)Yes\(f_2=b_2+b_3-b_6=1\)。
This means that in every update of the\(f_i\) priority activityg[a[i]] Each element in the\(x\)If\(x\) The number of prime factors is odd, indicating that the contribution is to be added, otherwise the contribution is subtracted. Similarly\(b_x\) The update also needs to takeg[a[i]] Each element in the\(x\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=1e6+5,mod=998244353;
int n;
int a[N],b[M],f[N];
vector<int> g[M],h[M];
void divide1(int x,int id)
{
for(int i=2;1ll*i*i<=x;i++)
{
if(x%i==0)
{
h[id].push_back(i);
while(x%i==0) x/=i;
}
}
if(x>1) h[id].push_back(x);
}
void divide2(int x,int id)
{
x=1;
for(auto t:h[id]) x*=t;
for(int i=2;1ll*i*i<=x;i++)
{
if(x%i==0)
{
g[id].push_back(i);
if(x!=i) g[id].push_back(x/i);
}
}
if(x>1) g[id].push_back(x);
}
void solve()
{
cin>>n;
int mx=0;
for(int i=1;i<=n;i++) cin>>a[i],mx=max(mx,a[i]);
for(int i=2;i<=mx;i++) divide1(i,i),divide2(i,i);
f[1]=1;
for(int i=1;i<=n;i++)
{
for(auto x:g[a[i]])
{
if(h[x].size()&1) f[i]=(f[i]+b[x])%mod;
else f[i]=(f[i]+mod-b[x])%mod;
}
for(auto x:g[a[i]]) b[x]=(b[x]+f[i])%mod;
}
cout<<f[n]<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("","r",stdin);
freopen("","w",stdout);
#endif
ios::sync_with_stdio(0);
(0);(0);
solve();
return 0;
}