开始重新板刷 AGC。别惦记着你那 b 多项式了！然后发现我做题量太少了。
现在思维强度不太上档次，T1 都能挂一个星期。
都干嘛呢？看了一圈，洛谷没人提交（除了 H_Kaguya 写了个左偏树），vjudge 也没人交题，真都写 APIO 呢？那咋 T1 没人交？
[AGC013A] Sorted Arrays
普及题。这种东西是真的容易写挂。这题红确实有点低。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <iostream>
using namespace std;
int n,ans,a[100010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int od=0;
for(int i=2;i<=n;i++){
if(a[i]==a[i-1])continue;
if(!od){
if(a[i]>a[i-1])od=1;
else od=-1;
}
else if(od==1){
if(a[i]>a[i-1])continue;
else ans++,od=0;
}
else{
if(a[i]<a[i-1])continue;
else ans++,od=0;
}
}
printf("%d\n",ans+1);
return 0;
}
[AGC013B] Hamiltonish Path
简单题，随便找一个点用力左右扩展即可。要 dfs 两次。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
int n,m,p[100010],q[100010];
bool v[100010];
struct node{
int v,next;
}edge[200010];
int t,head[100010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
void dfs(int x,int p[]){
v[x]=true;p[++p[0]]=x;
for(int i=head[x];i;i=edge[i].next){
if(!v[edge[i].v]){
dfs(edge[i].v,p);return;
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(1,p);dfs(1,q);
printf("%d\n",p[0]+q[0]-1);
for(int i=q[0];i>1;i--)printf("%d ",q[i]);
for(int i=1;i<=p[0];i++)printf("%d ",p[i]);puts("");
return 0;
}
[AGC013C] Ants on a Circle
首先两个蚂蚁碰到了改变方向这个可以看成两个蚂蚁互相穿过。这样位置是容易算的，不需要考虑相遇。只要找到第一只蚂蚁是哪个就好了。
假如有一只蚂蚁顺时针穿过了 \(0\) 位置，那么 \(1\) 号的位置就会往后一个，反之往前一个。这样只要算所有蚂蚁穿过 \(0\) 多少次就行了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n,l,t,st,ans[100010];
int main(){
scanf("%d%d%d",&n,&l,&t);
for(int i=0;i<n;i++){
int x,d;scanf("%d%d",&x,&d);
if(d==1)x+=t;
else x-=t;
st=(st+(int)floor(1.0*x/l)%n+n)%n;
ans[i]=(x%l+l)%l;
}
sort(ans,ans+n);
for(int i=0;i<n;i++)printf("%d\n",ans[(st+i)%n]);
return 0;
}
[AGC013D] Piling Up
比较逆天的。
首先显然的格路计数模型。然后每次操作可以看成增加 / 不变 / 减少一个黑球。这样设 \(dp_{i,j}\) 为 \(i\) 次操作剩下 \(j\) 个黑球的方案数就能简单 dp。
但是这样显然会重。一个神奇的 trick 是把所有相同形态折线中最低的一个看做答案，而最低的一个一定经过 \(0\)，于是只计算经过 \(0\) 的折线个数就不会重了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int mod=1000000007;
int n,m,dp[3010][3010][2];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)dp[0][i][0]=1;
dp[0][0][1]=1;
for(int i=1;i<=m;i++){
for(int j=0;j<=n;j++){
if(j){
dp[i][j][0]=(dp[i][j][0]+dp[i-1][j-1][0])%mod;
dp[i][j][1]=(1ll*dp[i][j][1]+dp[i-1][j-1][1]+dp[i-1][j][1])%mod;
if(j==1)dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][0])%mod;
else dp[i][j][0]=(dp[i][j][0]+dp[i-1][j][0])%mod;
}
if(j<n){
dp[i][j][1]=(1ll*dp[i][j][1]+dp[i-1][j+1][1]+dp[i-1][j][1])%mod;
if(!j)dp[i][j][1]=(dp[i][j][1]+dp[i-1][j+1][0])%mod;
else dp[i][j][0]=(1ll*dp[i][j][0]+dp[i-1][j+1][0]+dp[i-1][j][0])%mod;
}
}
}
int ans=0;
for(int i=0;i<=n;i++)ans=(ans+dp[m][i][1])%mod;
printf("%d\n",ans);
return 0;
}
[AGC013E] Placing Squares
大诈骗题。一开始一直看着这像个数学题，然后不会。然后看题解给我摆了一个矩阵上来，乐。
首先这个平方不好刻画，给它个组合意义。可以变成在一段里边放两个球，位置可以重。那 \(dp_{i,0/1/2}\) 为到 \(i\)，当前段放了 \(j\) 个球，转移显然。然后写个 \(3\times 3\) 矩阵递推这个 dp。标记点的转移式子把分段的情况去掉即可。
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int mod=1000000007;
int n,m,pos=-1;
struct node{
int a[4][4];
node(){memset(a,0,sizeof(a));}
node operator*(node s){
node ret;
for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)for(int k=1;k<=3;k++){
ret.a[i][j]=(ret.a[i][j]+1ll*a[i][k]*s.a[k][j])%mod;
}
return ret;
}
}a,b,ans;
node qpow(node a,int b){
node ans;for(int i=1;i<=3;i++)ans.a[i][i]=1;
while(b){
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
void solve(int x){
node ret=b*qpow(a,x-pos-1);
ans=ret*ans;pos=x;
}
int main(){
scanf("%d%d",&n,&m);
a.a[1][1]=a.a[1][3]=a.a[2][2]=a.a[3][1]=a.a[3][2]=1;
a.a[2][1]=a.a[2][3]=a.a[3][3]=2;
b.a[1][1]=b.a[2][2]=b.a[3][1]=b.a[3][2]=b.a[3][3]=1;
b.a[2][1]=2;
ans.a[1][1]=1;
for(int i=1;i<=m;i++){
int x;scanf("%d",&x);
node ret=b*qpow(a,x-pos-1);
ans=ret*ans;pos=x;
}
ans=qpow(a,n-pos-1)*ans;
printf("%d\n",ans.a[3][1]);
return 0;
}
[AGC013F] Two Faced Cards
我不会的题。是不是 AT 的题但凡上 3600 我就不会。
首先显然二分图匹配模型。用 Hall 定理转化问题，那么 \(X\) 的值可以变成给某个初始全 \(0\) 的序列 \(A\) 后缀 \(+1\)，\(Y\) 就是后缀 \(-1\)，最终如果 \(A\) 所有位置非负则合法。然后钦定每个位置先选 \(a\)，变成给定序列 \(A\) 和若干区间 \(+1\)，选尽量少的区间使得 \(A\) 非负。如果加上询问，枚举询问选哪一个，就变成需要 \(A\) 的一个前缀 \(\ge 0\)，剩下的 \(\ge -1\)。
那么接下来考虑哪些区间必须选。有一个自己做想不出来的结论：对于最大的 \(A_i<-1\) 的位置，选左端点最小的包含 \(i\) 的区间一定不劣。那么开个堆贪心即可。
剩下的就是全是 \(\ge -1\) 的了，那么对于每个前缀处理出使这个前缀都 \(\ge 0\) 最少选几个区间，同样可以贪心选右端点最靠右的，过程和上边大体相同。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
int n,m,a[100010],b[100010],c[100010],cnt[100010],s[100010],ans[100010];
bool vis[100010];
struct node{
int l,x;
bool operator<(const node&s)const{
return l<s.l;
}
bool operator>(const node&s)const{
return l>s.l;
}
};
priority_queue<node,vector<node>,greater<node> >q;
priority_queue<node>p;
vector<int>v[100010];
int main(){
scanf("%d",&n);n++;
for(int i=1;i<n;i++)scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
sort(c+1,c+n+1);
for(int i=1;i<n;i++){
a[i]=lower_bound(c+1,c+n+1,a[i])-c;
b[i]=lower_bound(c+1,c+n+1,b[i])-c;
cnt[a[i]]++;
}
for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1]-1;
for(int i=1;i<n;i++){
if(a[i]<=b[i])vis[i]=true;
else v[a[i]-1].push_back(i);
}
scanf("%d",&m);
int sum=0;
for(int i=n;i>=1;i--){
for(int x:v[i])q.push({b[x],x});
sum+=s[i];
while(cnt[i]+sum<-1){
while(!q.empty()&&q.top().l>i)q.pop();
if(q.empty()){
while(m--)puts("-1");
return 0;
}
vis[q.top().x]=true;
int l=b[q.top().x],r=a[q.top().x]-1;q.pop();
sum++;s[r]++;s[l-1]--;
ans[1]++;
}
}
sum=s[n+1];
for(int i=n;i>=1;i--){
sum+=s[i];s[i]=0;v[i].clear();
cnt[i]+=sum;
}
for(int i=1;i<n;i++){
if(!vis[i])v[b[i]].push_back(i);
}
sum=0;
for(int i=1;i<=n;i++){
ans[i+1]=ans[i];
for(int x:v[i])p.push({a[x]-1,x});
sum+=s[i];
bool jud=false;
while(cnt[i]+sum==-1){
while(!p.empty()&&p.top().l<i)p.pop();
if(p.empty()){
for(int j=i;j<=n;j++)ans[j+1]=n+1;
jud=true;break;
}
int l=b[p.top().x],r=a[p.top().x]-1;p.pop();
sum++;s[l]++;s[r+1]--;
ans[i+1]++;
}
if(jud)break;
}
while(m--){
int d,e;scanf("%d%d",&d,&e);
d=lower_bound(c+1,c+n+1,d)-c;
e=lower_bound(c+1,c+n+1,e)-c;
printf("%d\n",max(n-min(ans[d],ans[e]+1),-1));
}
return 0;
}