CCO板刷

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

作者：

CCCkk , 2024-08-27 14:46:33 , 所有人可见 , 阅读 29

考虑到很多题在网上几乎找不到题解，我相信这个计划是可以帮很多人从CCO的题目里学习的。

课程计划

2014

特洛伊和三角形

统计所有三角形明显是要从下面统计。

#include<bits/stdc++.h>
using namespace std;

const int N=2010;

char s[N][N];
int n,f[N][N];
long long ans;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i]+1;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=n;j++){
            if(s[i][j]=='#'){
                f[i][j]=1+min({f[i+1][j],f[i+1][j-1],f[i+1][j+1]});
                ans+=f[i][j];
            }
        }
    }
    cout<<ans;
    return 0;
}

国王格拉夫

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,m,a,b,st[N],s[N],dist[2][N];
struct Nd{
    int o,l;
    bool operator < (const Nd &B) const{
        return l>B.l;
    }
};
struct Ed{
    int x,y,l,c;
    bool operator < (const Ed &B) const{
        return dist[0][x]+l+dist[1][y]<dist[0][B.x]+B.l+dist[1][B.y];
    }
}eg[N];
vector<Nd> e[2][N];
void dijkstra(int S,int op){
    priority_queue<Nd> q;
    memset(dist[op],0x3f,sizeof dist[op]);
    memset(st, 0, sizeof st);
    q.push({S,0});
    dist[op][S]=0;
    while(q.size()){
        auto t=q.top();q.pop();
        if(st[t.o]) continue;
        st[t.o]=1;
        for(auto v:e[op][t.o]){
            if(dist[op][v.o]>dist[op][t.o]+v.l){
                dist[op][v.o]=dist[op][t.o]+v.l;
                q.push({v.o,dist[op][v.o]});
            }
        }
    }
}
signed main()
{
    cin>>n>>m>>a>>b;
    for(int i=1;i<=m;i++){
        int x,y,l,c;
        cin>>x>>y>>l>>c;
        e[0][x].push_back({y,l});e[1][y].push_back({x,l});
        eg[i]={x,y,l,c};
    }
    dijkstra(b,1);dijkstra(a,0);
    sort(eg+1,eg+m+1);
    for(int i=1;i<=m;i++) {
        s[i]=s[i-1]+eg[i].c;
    }
    int q;cin>>q;
    while(q--){
        int d;cin>>d;
        int l=0,r=m;
        while(l<r){
            int mid=l+r+1>>1;
            if(dist[0][eg[mid].x]+eg[mid].l+dist[1][eg[mid].y]<=d) l=mid;
            else r=mid-1;
        }
        cout<<s[l]<<"\n";
    }
    return 0;
}

狼人游戏

树形DP，只要知道当前结点是市民/狼人，以及子树中狼人数量信息就可以模仿树形背包的形式DP了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=220,mod=1e9+7;
int n,m,w,a,b,in[N],f[N][N][2],sz[N];
char op[2];
struct Pe{
    int o,w;
};
vector<Pe> e[N];
void dfs(int u){
    f[u][0][0]=f[u][1][1]=sz[u]=1;
    for(auto v:e[u]){
        dfs(v.o);
        sz[u]+=sz[v.o];
        for(int k=sz[u];k>=0;k--){
            int d0=0,d1=0;
            for(int t=min(sz[v.o],k);t>=0;t--){
                d0=(d0+f[u][k-t][0]*(f[v.o][t][0]+f[v.o][t][1]))%mod;
                if(v.w)d1=(d1+f[u][k-t][1]*f[v.o][t][0])%mod;
                else d1=(d1+f[u][k-t][1]*f[v.o][t][1])%mod;
            }
            f[u][k][0]=d0;f[u][k][1]=d1;
        }
    }
}
signed main(){
    cin>>n>>w>>m;
    for(int i=1;i<=m;i++){
        cin>>op>>a>>b;
        if(op[0]=='A')e[a].push_back({b,1});
        else e[a].push_back({b,0});
        in[b]++;
    }
    for(int i=1;i<=n;i++)
        if(!in[i]){
            e[0].push_back({i,1});
        }
    dfs(0);
    cout<<f[0][w][0];
}