不想做 AGC 的 F。感觉不如做 ARC 的 F。
有一说一我讲题确实比 nsc 稀烂。所以能不能让我不讲题。
[AGC015A] A+...+B Problem
显然。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <iostream>
using namespace std;
long long n,a,b;
int main(){
scanf("%lld%lld%lld",&n,&a,&b);
if(n==1&&a!=b){
puts("0");return 0;
}
if(a>b){
puts("0");return 0;
}
long long l=(n-1)*a+b,r=(n-1)*b+a;
printf("%lld\n",r-l+1);
return 0;
}
[AGC015B] Evilator
显然。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <iostream>
using namespace std;
int n;
char s[100010];
int main(){
scanf("%s",s+1);n=strlen(s+1);
long long ans=0;
for(int i=1;i<=n;i++){
if(s[i]=='U')ans+=(n-i)+(i-1<<1);
else ans+=(n-i<<1)+(i-1);
}
printf("%lld\n",ans);
return 0;
}
[AGC015C] Nuske vs Phantom Thnook
不显然。
树上连通块个数是点数减边数，然后显然。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
int n,m,q,sum[2010][2010],sumr[2010][2010],sumc[2010][2010];
char s[2010][2010];
int query(int x1,int y1,int x2,int y2){
return sum[x2][y2]+sum[x1-1][y1-1]-sum[x2][y1-1]-sum[x1-1][y2];
}
int queryr(int x1,int y1,int x2,int y2){
return sumr[x2][y2]+sumr[x1-1][y1]-sumr[x2][y1]-sumr[x1-1][y2];
}
int queryc(int x1,int y1,int x2,int y2){
return sumc[x2][y2]+sumc[x1][y1-1]-sumc[x2][y1-1]-sumc[x1][y2];
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(s[i][j]=='1');
sumr[i][j]=sumr[i-1][j]+sumr[i][j-1]-sumr[i-1][j-1]+(s[i][j]=='1'&&s[i][j-1]=='1');
sumc[i][j]=sumc[i-1][j]+sumc[i][j-1]-sumc[i-1][j-1]+(s[i][j]=='1'&&s[i-1][j]=='1');
}
}
while(q--){
int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int ans=query(x1,y1,x2,y2)-queryr(x1,y1,x2,y2)-queryc(x1,y1,x2,y2);
printf("%d\n",ans);
}
return 0;
}
[AGC015D] A or...or B Problem
咋 gap 这么大。
先把共通前缀干掉。然后显然是个数位 dp。假设 \(B\) 有 \(n\) 位。那么 \([A,2^n)\) 内的所有数可以构造出 \([A+2^n,2^{n+1})\) 内所有数。然后是 \(B\) 次高位 \(k\)，同样可以得到 \([2^n+2^k,2^n+2^{k+1})\) 所有数。容易发现接下来的位右端点就小于 \(r\) 没用了。还有一个 \([A,B]\)，答案就这三个区间。那打个并先。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define int long long
using namespace std;
int a,b;
signed main(){
scanf("%lld%lld",&a,&b);
if(a==b){
puts("1");return 0;
}
for(int i=61;i>=0;i--){
if(((a>>i)&1)!=((b>>i)&1)){
int l=a&((1ll<<i+1)-1),r=(1ll<<i)+l;
int tmp=i-1;
while(tmp>=0&&!((b>>tmp)&1))tmp--;
int ret=(1ll<<i)+(1ll<<tmp+1)-1;
if(r<=ret)printf("%lld\n",(1ll<<i+1)-l);
else printf("%lld\n",(1ll<<i+1)-r-l+ret+1);
return 0;
}
}
return 0;
}
[AGC015E] Mr.Aoki Incubator
新做的。把之前题解搬过来（然后把那篇指到这里）。
先考虑如果染一个 \(i\) 那么哪些会被染。显然是前边比后缀最小值走的快的和后边比前缀最大值走的慢的。这俩都是单调的，所以若设 \(dp_i\) 为选 \(i\) 的方案数，枚举上一次染 \(j\)，从 \(dp_j\) 转移过来，那么只有 \((j,i)\) 间速度在 \([premax_j,sufmin_i]\) 中的人不会被染色，这俩都是单调的，可以双指针维护。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int mod=1000000007;
int n,lsh[200010],dp[200010],sum[200010];
struct node{
int x,v;
bool operator<(const node&s)const{
return x<s.x;
}
}a[200010];
int l=1,r,L=1,R,cnt,mx[200010],mn[200010],pos[200010];
bool check(int l1,int r1,int L1,int R1){
if(l1>r1||L1>R1)return false;
while(r<r1){
r++;
if(a[r].v>=L&&a[r].v<=R)cnt++;
}
while(l<l1){
if(a[l].v>=L&&a[l].v<=R)cnt--;
l++;
}
while(R<R1){
R++;
if(pos[R]>=l&&pos[R]<=r)cnt++;
}
while(L<L1){
if(pos[L]>=l&&pos[L]<=r)cnt--;
L++;
}
return cnt;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].v),lsh[i]=a[i].v;
sort(a+1,a+n+1);sort(lsh+1,lsh+n+1);
for(int i=1;i<=n;i++)a[i].v=lower_bound(lsh+1,lsh+n+1,a[i].v)-lsh,pos[a[i].v]=i;
for(int i=1;i<=n;i++)mx[i]=max(mx[i-1],a[i].v);
mn[n+1]=n+1;
for(int i=n;i>=1;i--)mn[i]=min(mn[i+1],a[i].v);
dp[0]=sum[0]=1;
for(int i=1,l=0;i<=n+1;i++){
while(check(l+1,i-1,mx[l],mn[i]))l++;
dp[i]=(sum[i-1]-(l?sum[l-1]:0)+mod)%mod;
sum[i]=(sum[i-1]+dp[i])%mod;
}
printf("%d\n",dp[n+1]);
return 0;
}
[AGC015F] Kenus the Ancient Greek
你说的对，但是我不想做 AGC 的 F。反正巨大结论题做不出来。刚才做了个 AGC021 的 F 好像做出来了，但是确实少讨论 corner cases 了。那就是没做出来。那我太错。
最大值简单，斐波那契。数数不是很简单。
首先令 \(x\le y\)。假设点对 \((a,b)\) 能到最大值，那么把所有取一次 \(\gcd\) 之后能得到相同点对的缩成一个，即把 \((a,b),(a,a+b),(a,2a+b),\cdots\) 用 \((a,b)\) 表示。容易发现对于答案为 \(k\) 的可以缩成只有 \(k\) 个点对。构造这 \(k\) 个点对可以首先从前面的 \(k-1\) 个点对推一步，然后再加上一个 \((fib_k,fib_k+fib_{k+2})\)。算数是容易的，只要扫这 \(k\) 个点对除一下就行了。注意特判答案是 \(1\)，加上所有 \(a=b\)。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
#define int long long
using namespace std;
const int mod=1000000007;
int fib[110];
vector<pair<int,int> >v[110];
signed main(){
fib[0]=fib[1]=1;int cnt=0;
for(int i=2;;i++){
cnt=i;
fib[i]=fib[i-1]+fib[i-2];
if(fib[i]>1e18)break;
}
v[1].push_back(make_pair(1,2));
for(int i=2;i<=cnt;i++){
for(pair<int,int>p:v[i-1])v[i].push_back(make_pair(p.second,p.first+p.second));
v[i].push_back(make_pair(fib[i+1],fib[i-1]+fib[i+1]));
}
int q;scanf("%lld",&q);
while(q--){
int x,y;scanf("%lld%lld",&x,&y);
if(x>y)swap(x,y);
int mx=1;
while(mx+2<=cnt&&fib[mx+1]<=x&&fib[mx+2]<=y)mx++;
int ans=(mx==1)?(x%mod):0;
for(pair<int,int>p:v[mx]){
if(p.first<=x&&p.second<=y)ans=(ans+1ll*(y-p.second)/p.first+1)%mod;
if(p.second<=x)ans=(ans+1ll*(x-p.second)/p.first+1)%mod;
}
printf("%lld %lld\n",mx,ans);
}
return 0;
}