2019-03-29发表2019-03-29更新cf3 分钟读完 (大约407个字)

[cf548]Edgy Trees

Codeforces Round #548 (Div. 2)

C.Edgy Trees

题意

给一个树，树上的边分为黑色或者红色，现在我们定义一个序列[𝑎1,𝑎2,…,𝑎𝑘]

我们按照次序经过序列中的每一个点(最短路径)
如果进过至少一条黑边，那这个序列就是好的。

题解

至少一条的反义词就是一条都没有，这道题就是找没有黑边的子树。之后答案就是每个子树中的个数的$k$次方。

~~想着树形dp做，想了很久都没有写出来。~~

ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const ll mod = 1e9+7;
const int maxn = 1e5+10;
int cnt,n,k;
int head[maxn];
struct node{
    int next,to,val;
}G[maxn<<1];
void addedge(int u,int v,int val){
    G[cnt].next = head[u];
    G[cnt].to = v;
    G[cnt].val = val;
    head[u] = cnt++;
}
void init(){
    memset(head,-1,sizeof(head));
    cnt = 0;
}
int vis[maxn];
int t = 0;
void dfs(int u,int fa){
    t ++;
    vis[u] = 1;
    for(int i = head[u];~i;i=G[i].next){
        int v = G[i].to;
        if(v == fa) continue;
        if(vis[v]) continue;
        if(G[i].val == 0)dfs(v,u);
    }
}
ll pow3(ll a,ll b){
    ll res = 1;
    ll x = a;
    while(b){
        if(b&1) res  = res * x % mod;
        b >>= 1;
        x = x*x%mod;
    }
    return res;
}
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    init();
    scanf("%d%d",&n,&k);
    rep(i,0,n-1){
        int u,v,val; scanf("%d%d%d",&u,&v,&val);
        addedge(u,v,val); addedge(v,u,val);
    }
    ll ans = pow3(n,k);
    ll last = 0;
    rep(i,1,n+1){
        if(vis[i]==0) dfs(i,-1);
        ll temp = t - last;
        last = t;
        ans = (ans + mod - pow3(temp,k)) % mod;
    }
    printf("%lld\n",ans);
    return 0;
}

2019-03-06发表2019-03-06更新dfs2 分钟读完 (大约285个字)

[hdoj2260]Difficulty control(dfs)

Difficulty Control

题意

中文题目不说了。

题解

dfs+剪枝

剩下的加不到最优值剪掉
已经加过了最优值剪掉

~~我在大二的时候TLE了20次的题目终于在队友的指导之下完成了。~~

ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

ll n,m;
const int maxn = 30;
ll num[maxn];
vector<int> ve;
ll ans = INT_MAX;
int tans[maxn];
int temp[maxn];
void dfs(int x,ll now){
    if(abs(now-m) < ans && x == n){
        ans = abs(now-m);
        memcpy(tans,temp,sizeof(temp));
    }
    ll tt = 0;
    if(now-m > ans) return;
    rep(i,x,n) tt += num[ve[i]];
    if(tt + now + ans < m ) return ;
    if(x==n) {
        return ;
    }
    temp[ve[x]] = 1;
    dfs(x+1,now + num[ve[x]]);
    temp[ve[x]] = 0;
    dfs(x+1,now);
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    while(cin>>n>>m){
        ve.clear();
        memset(temp,0,sizeof(temp));
        memset(tans,0,sizeof(tans));
        rep(i,0,n){
            ll x; char ch; cin>>ch>>x;
            ve.push_back(ch-'A');
            num[ch-'A'] = x;
        }
        sort(ve.begin(),ve.end());
        ans = INT_MAX;
        dfs(0,0);
        vector<int> reans;
        rep(i,0,26) if(tans[i]) reans.push_back(i+'A');
        int len = reans.size();
        printf("%d\n",len);
        rep(i,0,len){
            printf("%c%c",reans[i],i==len-1?'\n':' ');
        }
    }
    return 0;
}

2019-03-05发表2019-03-05更新cf3 分钟读完 (大约425个字)

[cf541D]Gourmet choice (缩点+dfs)

Gourmet choice

题意

给定$n$个蛋糕和$m$个蛋糕，和他们之间的大小关系。问给所有的蛋糕一个可能最小的值，使得关系成立。

题解

首先由于有$=$的存在，有一些蛋糕的值是要一样的。所以我们需要把题目中的相等的点给缩到一起。

之后用dfs把值给确定下来。

其中缩点用到的技巧很厉害。

ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e3+10;
vector<int> e[maxn];
// m is behind of the n
int fa[maxn];
int Find(int x){
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
void Union(int i,int j){
    int x = Find(i);
    int y = Find(j);
    if(x!=y) fa[x] = y;
}
int ind[maxn],use[maxn],vis[maxn];
char mx[maxn][maxn];
int n,m;
// flag means the 矛盾
bool flag;
int dp[maxn];
void dfs(int x,int dep){
    if(flag) return ;
    dp[x] = max(dp[x],dep);
    for(auto to:e[x]){
        if(vis[to]) {
            flag = true;
            return ;
        }
        if(dep+1>dp[to]){
            vis[to] = 1;
            dfs(to,dep+1);
            vis[to] = 0;
        }
    }
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,0,n){
        scanf("%s",mx+i);
    }
    rep(i,0,n+m) fa[i] = i;
    rep(i,0,n)
        rep(j,0,m)
            if(mx[i][j] == '=')
                Union(i,n+j);
    rep(i,0,n) rep(j,0,m){
        int x = Find(i); int y = Find(j+n);
        if(mx[i][j] == '<'){
            e[x].push_back(y);
            ind[y] ++;
            use[x] = 1;
        }else if(mx[i][j] == '>'){
            e[y].push_back(x);
            ind[x] ++;
            use[y] = 1;
        }else{
            use[x] = 1;
        }
    }
    bool fflag = false;
    rep(i,0,n+m){
        if(use[i] && ind[i] == 0){
            fflag = true;
            vis[i] = 1;
            dfs(i,1);
            vis[i] = 0;
        }
    }
    if(fflag == false || flag){
        puts("No");
    }else{
        puts("Yes");
        rep(i,0,n) printf("%d ",dp[Find(i)]);
        puts("");
        rep(i,n,m+n) printf("%d ",dp[Find(i)]);
    }
    return 0;
}

[cf548]Edgy Trees

Codeforces Round #548 (Div. 2)

C.Edgy Trees

题意

题解

ac代码

[hdoj2260]Difficulty control(dfs)

Difficulty Control

题意

题解

ac代码

[cf541D]Gourmet choice (缩点+dfs)

Gourmet choice

题意

题解

ac代码

链接

分类

最新文章

归档

标签

订阅更新