Skip to content

AGC003 做题记录

A

每次走路距离至少为1，所以南北、东西必须同时出现才能回到原点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
char s[1005];
bool a,b,c,d;
int main(){
    scanf("%s",s+1);
    for(int i=1;s[i];++i){
        a|=(s[i]=='S');
        b|=(s[i]=='N');
        c|=(s[i]=='E');
        d|=(s[i]=='W');
    }
    puts((a==b&&c==d)?"Yes":"No");
    return 0;
}

B

考虑贪心。每种牌可以先自己消耗，如果还剩下一张牌，那么与后面一种牌配对最多会让后面那种牌浪费一张，这样操作比留下这张牌要更优（因为这张牌已经没用了），按该策略贪心即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e5+5;
int n,a[N];
ll ans;
int main(){
    n=read();
    rep(i,1,n)a[i]=read();
    rep(i,1,n){
        ans+=a[i]/2;
        a[i]%=2;
        if(a[i]&&a[i+1]){
            --a[i];--a[i+1];++ans;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

C

最小化操作一说明我们可以无限次使用操作二，不难发现这等价于交换 \(a_i,a_{i+2}\) 两个元素，也就是交换相邻的奇数或偶数下标的元素。这些对换可以生成所有奇数位和偶数位的置换，我们只需要对于排序前后的下标奇偶性不同的元素使用操作一即可。每次操作一可以减少两个这样的元素，所以答案要除以2。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e5+5;
struct node{int v,id;}a[N];
bool cmp(node a,node b){return a.v<b.v;}
int n,ans;
int main(){
    n=read();
    rep(i,1,n)a[i]={read(),i};
    sort(a+1,a+n+1,cmp);
    rep(i,1,n){
        if(i%2!=a[i].id%2)ans++;
    }
    printf("%d\n",ans/2);
    return 0;
}

D

有一说一这题没到黑题难度吧，算是比较常规的数论题（

对于每个正整数 \(x\) 我们考虑两种数，\(Pair(x)\) 表示与 \(x\) 相乘为立方数的最小正整数，而 \(Norm(x)\) 表示 \(x\) 去掉所有立方因子后的正整数。可以发现两个数如果拥有同样的 \(Norm\) ，那么也会有同样的 \(Pair\) ，也就是这两个数本质上是相同的。而如果一个数的 \(Norm\) 是另一个数的 \(Pair\) ，那么这两数显然不能同时选入答案。于是答案就是对于 \(s[i]\) 中所有本质不同的 \(x\) ，求 \(s[i]\) 中本质为 \(Norm(x)\) 或 \(Pair(x)\) 的个数的最大值。

下面考虑如何求解 \(Norm(x)\) ，其实只需要筛掉所有立方因子就可以了，也就是 \(\le 10^\frac{10}{3}\approx 2160\) 的质数的立方。筛完之后把这些质数剩下的次幂也从 \(x\) 中筛掉，并贡献给 \(Pair(x)\) 。由于剩下的因子大于原来 \(x^\frac{1}{3}\) ，推出最后剩下的 \(x\) 只有几类：

  • \(x\) 为质数
  • \(x\) 为质数的平方
  • \(x\) 为不同质数的积

对于第一类和第三类，容易得出 \(Pair(x)=x^2\) 。而对于第二类，\(Pair(x)=\sqrt x\) 。最后把这个数加入 \(Norm(x)\) 的桶里即可。

时间复杂度：\(O(N\frac{(MAX s_i)^\frac13}{\log MAX s_i})+O(N\log N)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N=1e5+10;
ll n,pri[N],tot;
ll a[N],b[N],ans;
bool vis[N];
map<ll,ll>mp;
int main(){
    n=read();
    rep(i,2,2160){
        if(!vis[i])pri[++tot]=i;
        for(int j=1;j<=tot&&pri[j]*i<=2160;j++){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
    rep(i,1,n){
        scanf("%lld",&a[i]);
        ll norm=1,pair=1;
        rep(j,1,tot){
            ll cube=pri[j]*pri[j]*pri[j];
            while(a[i]%cube==0)a[i]/=cube;
        }
        ++mp[a[i]];norm=a[i];
        rep(j,1,tot){
            if(a[i]%pri[j]!=0)continue;
            if(a[i]%(pri[j]*pri[j]))pair*=pri[j]*pri[j];
            else pair*=pri[j];
            while(a[i]%pri[j]==0)a[i]/=pri[j];
        }
        ll sqr=(ll)sqrt(a[i]);
        if(sqr*sqr!=a[i])pair*=a[i]*a[i];
        else pair*=sqr;
        a[i]=norm;b[i]=pair;
    }
    rep(i,1,n){
        if(a[i]==1)continue;
        ans+=max(mp[a[i]],mp[b[i]]);
        mp[a[i]]=mp[b[i]]=0;
    }
    printf("%lld\n",ans+!!mp[1]);
    return 0;
}

E

神仙题。

首先如果遇到了 \(A_{i+1}<A_i\) 的情况，那么不用考虑 \(A_i\) （因为后者取了更小的区间）。于是可以先用单调栈搞出一个单调递增的序列，这与原序列的操作是等价的。

不难发现第 \(i\) 次操作等价于重复目前的序列 \(\lfloor\dfrac{A_i}{A_{i-1}}\rfloor\) 次，然后再取原序列长度 \(d\equiv A_i\pmod{A_{i-1}}\) 的前缀。

问题在于这一小段不重复的前缀，而它在前面也一定是某一段 \(A_j\) 的重复出现。我们可以用类似的方法分解这段前缀，由于序列单调递增，我们可以找到满足 \(A_j<d,A_{j+1}>d\) 的 \(j\) 并且用它来取模，递归求解即可。

注意到每次取模 \(d\) 至少减小一半，递归到底时就是 \(1\) 到 \(d\) 的前缀对答案的贡献，可以用差分实现。

时间复杂度：\(O(n\log n)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,q,len;
ll A[N],F[N],tim[N];
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void Solve(ll d,ll w){
    int j=upper_bound(A+1,A+len+1,d)-A-1;
    if(!j) tim[1]+=w,tim[d+1]-=w;
    else F[j]+=d/A[j]*w,Solve(d%A[j],w);
}
int main(){
    n=read(),q=read();
    A[++len]=n;
    while(q--){
        ll x=read();
        while(len&&A[len]>=x) len--;
        A[++len]=x;
    }
    F[len]=1;
    for(int i=len;i>=2;i--) F[i-1]+=A[i]/A[i-1]*F[i],Solve(A[i]%A[i-1],F[i]);
    tim[1]+=F[1];tim[A[1]+1]-=F[1];
    for(int i=1;i<=n;i++) printf("%lld\n",tim[i]+=tim[i-1]);
}

F

首先看简单情形：

  • 当这个图形上下，左右拼接都是连通块，那么总连通块数为 \(1\) 。
  • 当这个图形上下，左右拼接都不是连通块，那么总连通块数为 \(cnt^{K-1}\) ，其中 \(cnt\) 为黑格数量。

唯一的问题就是这个图形上下和左右拼接只有一个是连通块的情况。不妨设左右连通。\(1\) 级分形的数量很好算而且是连通块，而我们又知道连通块数=黑点个数 - 边数，只用考虑如何统计边数。而上下不连通，所以答案就是 \(K-1\) 级分形中 黑点个数 - 左右相邻黑格的对数。

设原图左右相邻对数有 \(a\) 个，左右连通的行数为 \(b\) 。那么 \(K\) 级分形的左右连通行数为 \(K-1\) 分形的左右连通行数 \(\times b\) 。\(K\)级分形的相邻对数就是上级分形的相邻对数 \(\times b\) 加上黑格数量 \(\times a\) （黑格替换为原网格图）。

这个递推等价于用矩阵快速幂求 \(A=\begin{bmatrix} cnt &a \\ 0&b \end{bmatrix}^{K-1}\) ，答案为 \(A_{11}-A_{12}\) 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int P=1e9+7;
int n,m,cnt,s1,s2,flag1,flag2;
ll k;
char s[1005][1005];
ll fpow(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)res=res*x%P;
        y>>=1;x=x*x%P;
    }
    return res;
}
struct Matrix{
    ll a[3][3];
    Matrix(){memset(a,0,sizeof(a));}
    Matrix operator*(const Matrix &M){
        Matrix ans;
        rep(i,1,2)rep(j,1,2)rep(k,1,2)
        ans.a[i][j]=(ans.a[i][j]+a[i][k]*M.a[k][j]%P)%P;
        return ans;
    }
}A,ans;
int main(){
    n=read(),m=read(),k=read()-1;
    rep(i,1,n)scanf("%s",s[i]+1);
    rep(i,1,n){
        rep(j,1,m){
            if(s[i][j]=='#'){
                ++cnt;
                s1+=s[i][j-1]=='#';
                s2+=s[i-1][j]=='#';
            }
        }
        if(s[i][1]=='#'&&s[i][m]=='#')++flag1;
    }
    rep(i,1,m)if(s[1][i]=='#'&&s[n][i]=='#')++flag2;
    if(flag1&&flag2)return puts("1"),0;
    if(!flag1&&!flag2){
        printf("%lld\n",fpow(cnt,k));
        return 0;
    }
    if(!flag1)swap(flag1,flag2),swap(s1,s2);
    A.a[1][1]=cnt,A.a[1][2]=s1,A.a[2][2]=flag1;
    ans.a[1][1]=1,ans.a[2][2]=1;
    while(k){
        if(k&1)ans=ans*A;
        k>>=1;A=A*A;
    }
    printf("%lld\n",(ans.a[1][1]-ans.a[1][2]+P)%P);
    return 0;
}

Comments