• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

The 2019 China Collegiate Programming Contest Harbin Site (CCPC2019哈尔滨站)补题 | 题解

互联网 diligentman 6天前 5次浏览

咕咕咕 慢速补题中qwq

A- Gym 102394A Artful Paintings

简单的差分约束??
为什么过的人这么少qwq

#include<bits/stdc++.h>
using namespace std;
int T, n, m1, m2, t;
int head[3010], dis[3010], done[3010], cnt[3010];
int l[6010], r[6010], c[6010];
struct Edge{int nxt, to, dis;}edge[100010];
inline void add(int from, int to, int dis){
    edge[++t].nxt = head[from], edge[t].to = to, edge[t].dis = dis;
    head[from] = t;
}
inline void clear_graph(){
    memset(head, 0, sizeof(head));
    t = 0;
}
 
inline bool spfa(){
    queue<int>q;
    while(!q.empty()) q.pop();
    memset(dis, 0x3f, sizeof(int)*(n+1));
    memset(done, 0, sizeof(int)*(n+1));
    memset(cnt, 0, sizeof(int)*(n+1));
    q.push(0), dis[0] = 0, done[0] = 1, cnt[0] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        done[u] = 0;
        for(int i = head[u]; i; i = edge[i].nxt){
            int v = edge[i].to;
            if(dis[u] + edge[i].dis < dis[v]){
                dis[v] = dis[u] + edge[i].dis;
                if(dis[v] < 0) return false;
                if(!done[v]){
                    done[v] = 1;
                    q.push(v);
                    cnt[v]++;
                }
                if(cnt[v] > n) return false;
            }
        }
    }
    return true;
}
 
inline bool check(int x){//check if it's ok to have x painted
    clear_graph();
    for(int i = 1; i <= m1; i++) add(r[i], l[i] - 1, -c[i]);
    for(int i = m1 + 1; i <= m1 + m2; i++) add(l[i] - 1, r[i], x - c[i]);
    for(int i = 1; i <= n; i++) add(i - 1, i, 1);
    for(int i = 1; i <= n; i++) add(i, i - 1, 0);
    add(0, n, x);
    add(n, 0, -x);
    if(spfa() == false) return false;
    return true;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("ce.in", "r", stdin);
    #endif
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &n, &m1, &m2);
        for(int i = 1; i <= m1; i++){
            scanf("%d%d%d", &l[i], &r[i], &c[i]);
        }
        for(int i = 1; i <= m2; i++){
            scanf("%d%d%d", &l[i+m1], &r[i+m1], &c[i+m1]);
        }
        int L = 0, R = n;
        while(L < R){
            int mid = (L + R) / 2;
            if(check(mid)) R = mid;
            else L = mid + 1;
        }
        printf("%dn", R);
    }
    return 0;
}

B- Gym 102394B Binary Numbers

C- Gym 102394C Competition in Swiss-system

D- Gym 102394D Driverless Car

E- Gym 102394E Exchanging Gifts

#include<bits/stdc++.h>
#define MAXN 2000010
using namespace std;
int T,n,t;
int head[MAXN],ru[MAXN],done[MAXN];
long long dp[MAXN];
vector<int>a[MAXN];
struct Node{int nxt,to;}edge[MAXN<<1];
// unordered_map<int,long long>m[MAXN];
inline void add(int from,int to){
    // printf("add [%d %d]n",from,to);
    edge[++t].nxt=head[from],edge[t].to=to;
    head[from]=t;
}
inline void print(unordered_map<int,long long>cc){
    for(unordered_map<int,long long>::iterator it=cc.begin();it!=cc.end();it++){
        printf("sum of s[%d] is %lldn",(it->first),(it->second));
    }
    puts("");
}
inline void solve(int x){
    queue<int>q;
    while(!q.empty()) q.pop();
    q.push(x);
    while(!q.empty()){
        int u=q.front();q.pop();
        // printf("u=%dn",u);
        if(done[u]) continue;
        done[u]=1;
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].to;
            ru[v]--;
            dp[v]+=dp[u];
            if(ru[v]==0){
                q.push(v);
            }
        }
    }
}
inline int read()
{
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    // scanf("%d",&T);
    T=read();
    while(T--){
        // scanf("%d",&n);
        n=read();
        t=0;
        memset(head,0,sizeof(int)*(n+1));
        memset(ru,0,sizeof(int)*(n+1));
        memset(dp,0,sizeof(long long)*(n+1));
        memset(done,0,sizeof(int)*(n+1));
        memset(edge,0,sizeof(Node)*(n*2+1));
        for(int i=1;i<=n;i++) a[i].clear();
        long long ans=0;
        for(int k=1;k<=n;k++){
            int name;
            // scanf("%d",&name);
            name=read();
            a[k].push_back(name);
            if(name==1){
                int sum,cur;
                // scanf("%d",&sum);
                sum=read();
                // a[k].push_back(sum);
                for(int i=1;i<=sum;i++){
                    // scanf("%d",&cur);
                    cur=read();
                    a[k].push_back(cur);
                }
            }
            else if(name==2){
                int cur1,cur2;
                // scanf("%d%d",&cur1,&cur2);
                cur1=read(),cur2=read();
                a[k].push_back(cur1);
                a[k].push_back(cur2);
                add(k,cur1),add(k,cur2);
                ru[cur1]++,ru[cur2]++;
            }
        }
        // for(int i=1;i<=n;i++) printf("%d ",done[i]); puts("");
        dp[n]=1;
        for(int i=1;i<=n;i++)
            if((!done[i])&&(!ru[i]))
                solve(i);
        // for(int i=1;i<=n;i++) printf("dp[%d]=%dn",i,dp[i]);
        unordered_map<int,long long>ans_sum;
        ans_sum.clear();
        long long total=0;
        for(int i=1;i<=n;i++){
            if(a[i][0]==1){
                for(int j=1;j<a[i].size();j++){
                    // printf("%d ",a[i][j]);
                    ans_sum[a[i][j]]+=dp[i];
                }
                // puts("");
                // cout<<a[i].size()<<endl;
                total+=1ll*dp[i]*(a[i].size()-1);
            }
        }
        // printf("total=%lldn",total);
        ans=total;
        for(unordered_map<int,long long>::iterator it=ans_sum.begin();it!=ans_sum.end();it++){
            // printf("%d %dn",(it->first),(it->second));
            if((it->second)>total/2){
                ans=1ll*(total-(it->second))*2;
                break;
            }
        }
        printf("%lldn",ans);
    }
    return 0;
}

F- Gym 102394F Fixing Banners

从六个字符串中,每一个串找一位字符,问是否能拼出来"harbin"
使用dfs。时间复杂度最多是 1e6*6!

#include<bits/stdc++.h>
#define MAXN 2000010
using namespace std;
int n;
bool flag = false;
int  ex[7][7];
char a[7][MAXN];
inline int is(char x){
	if(x == 'h') return 1;
	if(x == 'a') return 2;
	if(x == 'r') return 3;
	if(x == 'b') return 4;
	if(x == 'i') return 5;
	if(x == 'n') return 6;
	else return 7;
}
inline void search(int x, vector<int>vec){
	if(flag == true) return;
	if(x == 7){
		flag = true;
		return;
	}
	for(int j = 0; j < vec.size(); j++){
		int u = vec[j];
		if(ex[x][u]){
			vector<int>tmp = vec;
			tmp.erase(tmp.begin() + j, tmp.begin() + j + 1);
			search(x + 1, tmp);
		}
	}
	return;
}
inline void clear(){
	flag = false;
	for(int i = 1; i <= 6; i++)
		for(int j = 1; j <= 6; j++)
			ex[i][j] = 0;
	return;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("ce.in", "r", stdin);
	#endif
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		clear();
		for(int j = 1; j <= 6; j++) scanf("%s", a[j]);
		for(int j = 1; j <= 6; j++){
			for(int k = 0; k <strlen(a[j]); k++){
				if(is(a[j][k]) <= 6) ex[j][is(a[j][k])] = 1;
			}
		}
		vector<int>vec; vec.clear();
		for(int j = 1; j <= 6; j++) vec.push_back(j);
		search(1, vec);
		if(flag == true) printf("Yesn");
		else printf("Non");
	}
	return 0;
}

G- Gym 102394G Game Store

H- Gym 102394H Highway Buses

I- Gym 102394I Interesting Permutation

序列四个限制条件:

  • 必须从0开始
  • 不能变小
  • 不能超过n-1,且最后一位必须为n-1
  • 第i位的数>=i-1
    之后如果和上一位不一样,相当于有向上或者向下两种情况,所以

    a

    n

    s

    2

    ans * 2

    ans2
    如果和上一位一样,那么在当前限制范围内选择数即可,

    a

    n

    s

    =

    a

    n

    s

    (

    a

    [

    i

    ]

    i

    +

    2

    )

    ans = ans * (a[i] – i + 2)

    ans=ans(a[i]i+2)

#include<bits/stdc++.h>
#define MAXN 100010
#define mod 1000000007
using namespace std;
int T, n;
int a[MAXN];
int main(){
	#ifndef ONLINE_JUDGE
	freopen("ce.in", "r", stdin);
	#endif
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
		long long ans = 1;
		for(int i = 1; i <= n; i++){
			if(i == 1 && a[i] != 0){
				ans = 0;
				break;
			}
			if(a[i] < i - 1 || a[i] >= n || a[i] < a[i - 1]){
				ans = 0;
				break;
			}
			else if(i != 1 && a[i] != a[i - 1]){
				ans = ans * 2 % mod;
			}
			else if(i != 1 && a[i] == a[i - 1]){
				ans = ans * (a[i] - i + 2) % mod;
			}
			else if(i == n && a[i] != n - 1) ans = 0;
		}
		printf("%lldn", ans);
	}
	return 0; 
}

J- Gym 102394J Justifying the Conjecture

  • 当n<=5的时候,一定是不能分成一个质数+一个合数的
  • 对于一个大于5的数n,先将其分成2和n-2
    • 如果n-2是合数,直接输出
    • 如果n-2是质数。因为n>5,所以n-2>2,一定是一个奇数。那么将n分为3和n-3,这是n-3必定为偶数,且>2(也就是合数了qwq)
#include<bits/stdc++.h>
#define MAXN 500010
using namespace std;
int T, n, cnt;
int not_prime[MAXN], prime[MAXN];
inline void init(){
	not_prime[1] = 1;
	for(int i = 2; i <= MAXN - 10; i++){
		if(not_prime[i] == 0){
			prime[++cnt] = i;
		}
		for(int j = 1; j <= cnt && prime[j] * i <= MAXN - 10; j++){
			not_prime[prime[j] * i] = 1;
			if(i % prime[j] == 0) break;
		}
	}
}
inline bool check(int x){
	for(int i = 1; i <= cnt && prime[i] * prime[i] <= x; i++){
		if(x % prime[i] == 0) return false;
	}
	return true;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("ce.in", "r", stdin);
	#endif
	scanf("%d", &T);
	init();
	while(T--){
		scanf("%d", &n);
		if(n <= 5) printf("-1n");
		else{
			int a = 2, b = n - 2;
			if(check(b) == true){
				a = 3, b = n - 3;
			}
			printf("%d %dn", a, b);
		}
	} 
	return 0;
}

K- Gym 102394K Keeping Rabbits

我们设sum为所有兔子体重的总和。
每只兔子过了每天之后期望变成:

w

i

+

w

i

s

u

m

i

1

w_i + frac{wi}{sum_i} * 1

wi+sumiwi1
因为每天sum都要增加1,所以所有的兔子加号后面的总和就是1。而他们的分母sum都是一样的,相当于是按照自己的体重wi来加权均分。
一开始的体重可以看做一共有sum份,按照一定的比例均分了体重。
之后的每一天都是按照前一天的体重来增加,也就是:按照相同的比例均分体重。
所以归纳起来,就是一共有sum+k的体重,按照最初的体重比例进行了均分。

#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int T, n, k;
int a[MAXN];
long long sum1, sum2;
int main(){
	#ifndef ONLINE_JUDGE
	freopen("ce.in", "r", stdin);
	#endif
	scanf("%d", &T);
	while(T--){
		sum1 = 0;
		scanf("%d%d", &n, &k);
		for(int i = 1; i <= n; i++){
			scanf("%d", &a[i]);
			sum1 += a[i];
		}
		sum2 = sum1;
		sum1 += k;
		for(int i = 1; i <= n; i++) printf("%.8lf ", 1.0 * sum1  * a[i] / sum2);
		puts("");
	} 
	return 0;
}

L- Gym 102394L LRU Algorithm


喜欢 (0)