AtCoder Beginner Contest 179 總結

A - Plural Form

模擬簽到題1

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int main()
{
    IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        string s;
        cin>>s;
        if(s.back()=='s') s+="es";
        else s+="s";
        cout<<s<<'\n';
    }
    return 0;
}

B - Go to Jail

簽到題2

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int main()
{
    IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        int cnt=0;
        bool ok=0;
        while(n--)
        {
            int a,b;
            cin>>a>>b;
            if(a==b) 
            {
                cnt++;
                if(cnt==3) ok=1; 
            }
            else cnt=0;
        }
        if(ok) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

C - A x B + C

$A\times B+C=N$不難發現只要有$A\times B<N$，就會有一組解。因此列舉$A$隨便求求即可

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
int main()
{
    IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        ll res=0;
        for(int i=1;i<=n;i++)
        {
            ll now=n/i;
            if(n%i==0) now--;
            res+=now;
        }
        cout<<res<<'\n';
        
    }
    return 0;
}

D - Leaping Tak

動態規劃上樓梯升級版
狀態表示：$f_i$表示目前在第$i$個位置的集合
狀態轉移：列舉可以從哪些位置過來即可，字首和優化!

// O(nk)
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#define l first
#define r second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=200010;
const ll mod=998244353;
int n,k;
ll f[N],s[N];
pii a[N];
int main()
{
    IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;
        f[1]=1;
        s[1]=1;
        for(int i=2;i<=n;i++)
        {
            for(int j=1;j<=k;j++)
                f[i]=(f[i]+s[max(0,i-a[j].l)]-s[max(0,i-a[j].r-1)])%mod;;
            s[i]=(s[i-1]+f[i])%mod;
        }    
        cout<<(f[n]+mod)%mod<<'\n';
    }
    return 0;
}

E - Sequence Sum

$N\le 10^{10}$非常大，一定不能暴力列舉，不過$M\le 10^5$非常小，這意味這餘數最多有$10^5$情況，由此對於每一個所求的每一個$A_i$必定會出現迴圈節，只需要找到迴圈節即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
ll n,x,m;
int st[N];
ll s[N];
int main()
{
    IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>x>>m;
        ll l,r;
        for(ll a=x,k=1;;a=a*a%m,k++)
        {
            if(!st[a]) st[a]=k;
            else
            {
                l=st[a],r=k-1;
                break;
            }
            s[k]=s[k-1]+a;
        }
        ll len=r-l+1;
        ll res=0;
        res+=s[min(n,l-1)];
        n=max(0ll,n-l+1);
        if(n) res+=(s[r]-s[l-1])*(n/len)+(s[n%len+l-1]-s[l-1]);
        cout<<res<<'\n';
    }
    return 0;
}

F - Simplified Reversi

還沒看，明天看
維護兩個陣列row[]和col[]，row[i]表示第i行目前能夠覆蓋到哪一列。
考慮每次操作，如果目前在第x列（opt=1）放置，那麼對於行來說就有一部分被截斷，不難知道$[1,mrow]$被截斷，因此需要在row[]進行區間修改，答案會減去col[x]-2需要單點詢問，由此只需要用線段樹維護這兩個陣列即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200010;
int n,q;
struct Segment
{
    struct node
    {
        int l,r,val,lazy;
    }tree[N*4];
    void build(int u,int l,int r)
    {
        tree[u]={l,r,n,n+1};
        if(l==r) return;
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }
    void pushdown(int u)
    {
        if(tree[u].lazy==n+1) return;
        tree[u<<1].val=min(tree[u<<1].val,tree[u].lazy);
        tree[u<<1|1].val=min(tree[u<<1|1].val,tree[u].lazy);     
        tree[u<<1].lazy=min(tree[u<<1].lazy,tree[u].lazy);
        tree[u<<1|1].lazy=min(tree[u<<1|1].lazy,tree[u].lazy);
        tree[u].lazy=n+1;
    }
    void modify(int u,int l,int r,int val)
    {
        if(tree[u].l>=l&&tree[u].r<=r)
        {
            tree[u].lazy=min(tree[u].lazy,val);
            tree[u].val=min(tree[u].val,val);
            return;
        }
        pushdown(u);
        int mid=tree[u].l+tree[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,val);
        if(r>mid) modify(u<<1|1,l,r,val);
    }
    int query(int u,int p)
    {
        if(tree[u].l==tree[u].r) return tree[u].val;
        pushdown(u);
        int mid=tree[u].l+tree[u].r>>1;
        if(p<=mid) return query(u<<1,p);
        else return query(u<<1|1,p);
    }
}row,col;
int mrow,mcol;
int main()
{
    IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>q;
        row.build(1,1,n);
        col.build(1,1,n);
        ll res=1ll*(n-2)*(n-2);
        mcol=mrow=n;
        while(q--)
        {
            int op,x;
            cin>>op>>x;
            if(op==1)
            {
                mcol=min(mcol,x);
                res-=col.query(1,x)-2;
                row.modify(1,1,mrow,x);
            }
            else
            {
                mrow=min(mrow,x);
                res-=row.query(1,x)-2;
                col.modify(1,1,mcol,x);
            }
        }
        cout<<res<<'\n';
    }
    return 0;
}

此題貌似我的解法非常複雜，不過我太菜只能用這種稍微暴力的資料結構維護，我 貪心啥的貪心不出來啊啊啊
要加油哦~