ABC_216
C - Many Balls
思路：
二进制表示
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
ll n;
int a[100];
string ans;
int main(){
cin>>n;
ll t=n,tot=0;
while(t){
a[++tot]=t%2;
t=t/2;
}
//for(int i=tot;i>=1;i--) cout<<a[i];
//cout<<"\n";
ans="";
int ok=1;
for(int i=tot;i>=1;i--){
if(ok&&a[i]==1) ans+='A',ok=0;
else if(a[i]==1) ans+="BA";
else ans+='B';
}
cout<<ans<<"\n";
}D - Pair of Balls
思路：
建图，用$map$标记小球相同颜色的个数进队列，按优先队列$push$进去，跑拓扑序，每次删点要将新的点$push$到队列
代码：
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair <int,int> pll;
const int N=2e5+7;
int n,m,vis[N];
vector <int> ho[N];
vector <int> cnt[N];
int TOPO(){
priority_queue <pll> q;
for(int i=1;i<=m;i++){
int id=ho[i].back();ho[i].pop_back();
q.push(pll(cnt[id].size(),id));
}
int ac=1;
while(!q.empty()){
pll it=q.top();q.pop();
int id=it.se;
if(vis[id]) continue;
if(cnt[id].size()>1){
vis[id]++;
int p1=cnt[id][0],p2=cnt[id][1];
if(ho[p1].size()){
int idx=ho[p1].back();ho[p1].pop_back();
cnt[idx].push_back(p1);
q.push(pll(cnt[idx].size(),idx));
}
if(ho[p2].size()){
int idx=ho[p2].back();ho[p2].pop_back();
cnt[idx].push_back(p2);
q.push(pll(cnt[idx].size(),idx));
}
}else{
ac=0;
break;
}
}
return ac;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int k,x;
scanf("%d",&k);
for(int j=1;j<=k;j++){
scanf("%d",&x);
ho[i].push_back(x);
}
reverse(ho[i].begin(),ho[i].end());
cnt[ho[i][k-1]].push_back(i);
}
if(TOPO()) puts("Yes");
else puts("No");
}E - Amusement Park
思路：
很容易看出每次都去$A_i$最大的地方，我们可以先排个序，然后去二分个$x$表示大于等会$x$的要修改至$x$。然后去$check$看还剩多少次数$cnt$，最加上$x+1$的贡献。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+7;
int n,k,cnt;
ll a[N];
int check(ll mid){
ll sum=0;
for(int i=1;i<=n;i++){
sum=sum+max(0ll,a[i]-mid+1);
}
if(sum<=k){
cnt=k-sum;
return 1;
}else{
return 0;
}
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
ll l=0,r=2e9,up=0;
sort(a+1,a+1+n);reverse(a+1,a+1+n);
while(l<=r){
ll mid=(l+r>>1);
if(check(mid)) up=mid,r=mid-1;
else l=mid+1;
}
ll res=0;
for(int i=1;i<=n;i++){
ll t=max(0ll,a[i]-up+1);
if(i<=cnt){
if(up>0) res=res+(a[i]+up-1)*(t+1)/2ll;
else res=res+(a[i]+up)*t/2ll;
}else{
res=res+(a[i]+up)*t/2ll;
}
}
cout<<res<<"\n";
}
F - Max Sum Counting
思路：
可以看出这题其实是个背包问题，在前$i$个中必选$B_i$的贡献就是答案
代码：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N=5010;
const int mod=998244353;
struct node{int v,w;}a[N];
int n,f[N][N];
bool cmp(node x,node y){return x.v<y.v;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].v);
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i].w);
}
sort(a+1,a+1+n,cmp);
f[0][0]=1;
int ans=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=5000;j++){
if(a[i].w<=j){
f[i][j]=(f[i-1][j]+f[i-1][j-a[i].w])%mod;
if(j<=a[i].v) ans=(ans+f[i-1][j-a[i].w])%mod;
}else{
f[i][j]=(f[i][j]+f[i-1][j])%mod;
}
}
}
printf("%d\n",ans);
}G - 01Sequence
思路：
可以看出，我们应该贪心的将$1$的数量放在最后面开始放,我们可以用树状数组在实现区间查询修改，用并查集来支持从最右边开始单点修改的位置。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e5+7;
struct node{int l,r,x;}a[N];
int n,m,Ans[N],tr[N],f[N];
int lowbit(int i){return i&(-i);}
int fin(int x){return f[x]==x? x:f[x]=fin(f[x]);}
void add(int x){
for(int i=x;i<=n;i+=lowbit(i)) tr[i]++;
}
int ask(int x){
int sum=0;
for(int i=x;i;i-=lowbit(i)) sum=sum+tr[i];
return sum;
}
bool cmp(node x,node y){
return x.r<y.r;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i].l>>a[i].r>>a[i].x;
}
for(int i=0;i<=n;i++) f[i]=i;
sort(a+1,a+1+m,cmp);
for(int i=1;i<=m;i++){
int lim=a[i].x-(ask(a[i].r)-ask(a[i].l-1));
for(int j=1;j<=lim;j++){
int u=fin(a[i].r);
add(u),Ans[u]=1;
f[u]=fin(u-1);
}
}
for(int i=1;i<=n;i++) cout<<Ans[i]<<" ";
cout<<"\n";
}
ABC_127
D - Cutting Woods
思路：
我们可以反过来思考下，他将木棒则断，意思就是将集合一分为二，然后查询就是询问集合大小，那我们就可以离线处理下，然后反过来询问，就是合并集合，可用并查集维护，然后数据比较大要离散化处理。
ps:貌似multiset可以直接写
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=2e5+7;
struct node{int c,x;}q[N];
int n,m;
int a[N],cnt[N],f[N];
int fin(int x){return f[x]==x? x:f[x]=fin(f[x]);}
vector <int> Ans,ho;
void bing(int x,int y){
int f1=fin(x),f2=fin(y);
if(f1==f2) return;
f[f2]=f1,cnt[f1]+=cnt[f2];
}
int get(int x){return lower_bound(ho.begin(),ho.end(),x)-ho.begin()+1;}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>q[i].c>>q[i].x;
if(q[i].c==1){
ho.push_back(q[i].x);
}
}
ho.push_back(n);
sort(ho.begin(),ho.end());
ho.erase(unique(ho.begin(),ho.end()),ho.end());
int idx=1;
for(int i=0;i<ho.size();i++){
f[i+1]=i+1;
cnt[i+1]=(ho[i]-idx+1);
idx=ho[i]+1;
}
for(int i=m;i>=1;i--){
if(q[i].c==1){
bing(get(q[i].x),get(q[i].x)+1);
}else{
Ans.push_back(cnt[fin(get(q[i].x))]);
}
}
reverse(Ans.begin(),Ans.end());
for(auto p:Ans) cout<<p<<"\n";
}E - Sorting Queries
思路：
用队列和multiset模拟处理即可。
代码：
#include <iostream>
#include <set>
#include <queue>
using namespace std;
int m;
multiset <int> sa;
queue <int> q;
int main(){
cin>>m;
int cnt=0,ch=0;
while(m--){
int op,x;
cin>>op;
if(op==1){
cin>>x;
q.push(x);
++ch;
}else if(op==2){
if(cnt){
auto it=sa.lower_bound(-1);
cout<<*it<<"\n";
cnt--;
sa.erase(it);
}else{
int p=q.front();q.pop();
cout<<p<<"\n";
ch--;
}
}else{
cnt=cnt+ch;
ch=0;
while(!q.empty()) sa.insert(q.front()),q.pop();
}
}
}
F - Make Pai
思路：
状态划分：$dp[i][j]$为i到j配对完的的方案数
我们让i去找个k配对，那么其中间的一定也要配对完才能选[i+1,k-1],即可 将其划分[i+1,k-1]和[k+1,j]两个集合,然后进行状态转移。
状态转移：$dp[i][j]=dp[i+1][k-1]*dp[k+1][j]*C_{x+y+1}^{x}$其中$x=k-i-1>>1,y=j-k>>1$。
$C_{j-i+1}^{j-k+1}$，的意义是两个集合中有x和y+1个配对放x+y+1个位置的方案。
代码：
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=410;
int n,m,e[N][N];
ll f[N][N],fac[2000010];
ll ksm(ll x,ll p){
ll res=1;
while(p){
if(p%2==1) res=res*x%mod;
p/=2;
x=x*x%mod;
}
return res;
}
ll inv(ll a) {
return ksm(a,mod-2)%mod;
}
ll C(ll n,ll k){
if(k>n)return 0;
if(k==1)return n;
return (fac[n]*inv(fac[k])%mod*inv(fac[n-k])%mod);
}
ll dfs(int l,int r){
if(l>r) return 1;
if(f[l][r]!=-1) return f[l][r];
ll ans=0;
for(int i=l+1;i<=r;i+=2){
int x=i-l-1>>1,y=r-i>>1;
if(!e[l][i]) continue;
ans=(ans+1ll*dfs(l+1,i-1)*dfs(i+1,r)%mod*1ll*C(x+y+1,y)%mod)%mod;
}
return f[l][r]=ans;
}
int main(){
cin>>n>>m;
memset(f,-1,sizeof f);
fac[0] = 1;
for(int i = 1;i < 2000006; i++) {
fac[i] = (fac[i-1]*i)%mod;
}
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
e[u][v]=e[v][u]=1;
}
cout<<dfs(1,2*n)<<"\n";
}
G - Groups
思路：
这题分组，我们可以向推斯特林数的递推一样推这题。
状态划分：$f[i][j]$为1-i个人合法划分j组的方案。
当一个人要进入分组的时候，他可以单独分为一组，或者可以放入前面合法组中。
状态转移：$f[i][j]=f[i-1][j-1]+f[i-1][j]*(j-\frac{i-1}{m})$
代码：
#include <iostream>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=5010;
int n,m;
int f[N][N];
int main(){
scanf("%d %d",&n,&m);
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=(f[i-1][j-1]+1ll*f[i-1][j]*(j-(i-1)/m)%mod)%mod;
}
}
for(int i=1;i<=n;i++){
printf("%d\n",f[n][i]);
}
}
ABC_218
D - Rectangles
我们可以按$x_i$排个序，然后和扫描线一样从前往后扫，用个$map$标记$y_i$相等的点，然后计算答案。
代码：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N=2010;
int n;
int x[N],y[N],ma[N];
vector <int> ho,G[N];
int get(int x){
return lower_bound(ho.begin(),ho.end(),x)-ho.begin()+1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&x[i],&y[i]);
ho.push_back(x[i]);ho.push_back(y[i]);
}
sort(ho.begin(),ho.end());
ho.erase(unique(ho.begin(),ho.end()),ho.end());
for(int i=1;i<=n;i++){
x[i]=get(x[i]);
y[i]=get(y[i]);
G[x[i]].push_back(y[i]);
}
ll ans=0;
for(int i=1;i<=n;i++){
for(auto p:G[i]){
ma[p]++;
}
for(int j=1;j<=i-1;j++){
int cnt=0;
for(auto p:G[j]){
if(ma[p]) ans=ans+cnt,cnt++;
}
}
for(auto p:G[i]){
ma[p]--;
}
}
printf("%lld\n",ans);
}E - Destruction
思路：
有负边的最小生成树，负边必选，然后跑最小生成树。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+7;
struct node{
int u,v,w;
bool operator<(const node &t)const{
return w<t.w;
}
}e[N];
int n,m,f[N];
int fin(int x){return f[x]==x? x:f[x]=fin(f[x]);}
int bing(int x,int y){
int f1=fin(x),f2=fin(y);
if(f1==f2) return 0;
f[f2]=f1;
return 1;
}
int main(){
scanf("%d %d",&n,&m);
ll sum=0;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
sum=sum+e[i].w;
}
sort(e+1,e+1+m);
for(int i=1;i<=n;i++) f[i]=i;
ll ans=0;
for(int i=1;i<=m;i++){
if(bing(e[i].u,e[i].v)||e[i].w<=0){
ans=ans+e[i].w;
}
}
printf("%lld\n",sum-ans);
}F - Blocked Roads
思路：
首先bfs跑个最短路，标记最短路，询问时如果不是标记的最短路，则ans为最短路，否则跑bfs再跑最短路。因为最短路最长为n，所以时间复杂度为$log(nm)$
代码：
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N=500;
int n,m,s[N*N],d[N*N],f[N],pre[N],vis[N];
int e[N][N];
vector <int> G[N];
int bfs(){
queue <int> q;
for(int i=1;i<=n;i++) f[i]=0,vis[i]=0;
q.push(1);vis[1]=1;
while(!q.empty()){
int p=q.front();q.pop();
for(auto v:G[p]){
if(!vis[v]){
f[v]=f[p]+1;
vis[v]=1;
pre[v]=p;
q.push(v);
}
}
}
if(f[n]==0) return -1;
else return f[n];
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d %d",&u,&v);
s[i]=u,d[i]=v;
e[u][v]=1;
G[u].push_back(v);
}
int ans=bfs();
int ne=n;
while(ne>=1){
int t=pre[ne];
e[t][ne]=0;
ne=t;
}
for(int i=1;i<=m;i++){
if(e[s[i]][d[i]]){
printf("%d\n",ans);
continue;
}
for(int j=0;j<G[s[i]].size();j++)
if(G[s[i]][j]==d[i]){
G[s[i]].erase(G[s[i]].begin()+j);
break;
}
printf("%d\n",bfs());
G[s[i]].push_back(d[i]);
}
}
G - Game on Tree 2
思路：
首先中位数为跟到叶子节点的树链的中位数， 我们能用主席树算出，然后根据中位数来树形dp，深度为奇数则是Alice操作选中位数最大，偶数为BOb操作选中位数最小。
代码
#include <iostream>
#include <vector>
#include <algorithm>
#define mid (l+r>>1)
using namespace std;
const int N=1e5+7;
int n,tot,a[N],rt[N],f[N];
struct node{int lc,rc,v;}tr[40*N];
vector <int> G[N],ho;
int get(int x){return lower_bound(ho.begin(),ho.end(),x)-ho.begin()+1;}
void insert(int &k,int pr,int l,int r,int p){
k=++tot;tr[k]=tr[pr],tr[k].v++;
if(l==r) return;
if(p<=mid) insert(tr[k].lc,tr[pr].lc,l,mid,p);
else insert(tr[k].rc,tr[pr].rc,mid+1,r,p);
}
int ask(int k,int l,int r,int key){
if(l==r) return l;
int tem=tr[tr[k].lc].v;
if(tem>=key) return ask(tr[k].lc,l,mid,key);
else return ask(tr[k].rc,mid+1,r,key-tem);
}
void dfs(int p,int fa,int dep){
insert(rt[p],rt[fa],1,n,get(a[p]));
int ok=1;
if(dep&1) f[p]=0;
else f[p]=1e9;
for(auto v:G[p]){
if(v==fa) continue;
dfs(v,p,dep+1);
ok=0;
if(dep&1){
f[p]=max(f[p],f[v]);
}else{
f[p]=min(f[p],f[v]);
}
}
if(ok){
if(dep&1){
f[p]=ho[ask(rt[p],1,n,(dep+1)/2)-1];
}else{
f[p]=(ho[ask(rt[p],1,n,(dep+1)/2)-1]+ho[ask(rt[p],1,n,(dep+1)/2+1)-1])/2;
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ho.push_back(a[i]);
}
for(int i=1;i<=n-1;i++){
int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
ho.erase(unique(ho.begin(),ho.end()),ho.end());
sort(ho.begin(),ho.end());
dfs(1,0,1);
printf("%d\n",f[1]);
}
ARC_125
A - Dial Up
思路：
他选择一定在$01$之间摇摆，否则不能组成，我们可以大胆的dfs去搜索。
代码：
#include <iostream>
using namespace std;
const int N=2e5+7;
int n,m;
int a[N],b[N];
int dfs(int p1,int p2){
if(p2==m) return 0;
int ans=-1e9;
for(int i=0;i<=n-1;i++){
if(b[p2]==a[(p1+i)%n]){
ans=dfs((p1+i)%n,p2+1)+1+i;
break;
}else if(b[p2]==a[(p1-i+n)%n]){
ans=dfs((p1-i+n)%n,p2+1)+1+i;
break;
}
}
return ans;
}
void solve(){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<m;i++) scanf("%d",&b[i]);
int ans=dfs(0,0);
if(ans>=0) printf("%d\n",ans);
else puts("-1");
}
int main(){
solve();
}
B - Squares
思路：
如题要求$x^2-y=z^2$，$z$的个数，我们将其化为：$x^2-z^2=y$，则求的是平方数之间的差值有多少不同的情况，易知差值其为等差数列，枚举平方数之间的间隔，通过公式来计算答案。
代码：
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll n;
int main(){
cin>>n;
ll ans=0;
ll s=0;
for(ll i=1;;i++){
s+=2;
if(n-(i*i-s)<0) break;
ans=(ans+(n-(i*i-s))/s)%mod;
}
printf("%lld\n",ans);
}
C - LIS to Original Sequence
思路：
题目给出$LCS$，我们可以得出在$A_i$到$A_{i+1}$之间肯定是递减的序列，且不属区间$[A_i,A_{i+1}]$，这样保证了$LCS$不会增大。然后题目要构造字典序最小，我们就将能放在$A_i,A_{i+1}$之间的数放一个最小的放在总结，其余的以降序放在$A_n$之后
代码：
#include <iostream>
using namespace std;
const int N=2e5+7;
int k,n,a[N],B[N];
int main(){
cin>>n>>k;
for(int i=1;i<=k;i++) cin>>a[i];
int j=1;
for(int i=1;i<k;i++){
printf("%d ",a[i]);
B[a[i]]=1;
while(B[j]) j++;
if(j<a[i]){
printf("%d ",j);
B[j]=1;
while(B[j]) j++;
}
}
for(int i=n;i>=1;i--) if(!B[i]) printf("%d ",i);
puts("");
}