GRYZ10.27模拟赛解题报告

目录

期望得分:\(0 \sim 100 + 30 + 30 = 60 \sim 160pts\)
实际得分:\(20 + 0 + 30 = 50pts\)

被凯神吊打了/kk

是啊,我怎可能与神同肩。

前两道题都需要发现关键性质来做,第三个是真不会了。

T1 - job

你要发现这么一个性质:对于每一天,要么不工作,要么工作七小时。

然后你把问题转化成 “每连续七天至少工作一小时” 进行 DP 就好了。

设 \(f_i\) 表示到第 \(i\) 天并在第 \(i\) 天工作一小时的最小消耗精力。

转移方程:

\[f_i = \displaystyle\min_{1 \le j \le 7} \{ f_{i-j} + a_i \} \]

这个本可以单调队列优化的,但因为 \(j\) 的范围只有 \(7\),所以加不加没啥意思。

/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

int n, ans;
int a[MAXN];
int f[MAXN];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

signed main()
{
    int T = read();
    while(T--) {
        ans = 0x3f3f3f3f3f3f3f3f;
    	n = read();
    	for(int i = 1; i <= n; ++i) a[i] = read();
    	memset(f, 0x3f, sizeof f);
    	f[0] = 0;
    	for(int i = 1; i <= n; ++i) {
    	    for(int j = 1; j <= min(i, 7ll); ++j) {
    	        f[i] = min(f[i], f[i - j] + a[i]);
            }
        }
        for(int j = 1; j <= 7; ++j) {
            ans = min(ans, f[n - j + 1]);
        }
        printf("%lld\n", ans * 7);
    }
    return 0;
}

T2 - ball

我们先做这样的建模: 把每个篮子看成图上的一个点,把球看成连接两个篮子代表的点的边。我们就变成了要计算一个这样的问题:给一张图 \(G = (V,E)\),可以把每条边分配给一个相邻的结点,每个结点只能有一条边分配给它,问有多少种分配边的方案数?

显然,不同的连通分量之间互不影响,我们只需要计算每一个连通分量的答案,再把它们的答案按乘法原理分别乘起来即可。

  • 对于 \(E > V\) 的联通分量来说,方案数为 \(0\)。
  • 对于 \(E = V\) 的联通分量来说,如果存在自环,方案数为 \(1\),否则为 \(2\)。
  • 对于 \(E = V - 1\) 的联通分量来说,如果依次把每个点看做根节点,然后整棵树向下坠,每条边只有一条分配方式。这种情况一共有 \(V\) 次,所以方案数为 \(V\)。

所以我们只需要写一个并查集或者 DFS 就能解决问题。

/*
Work by: Suzt_ilymtics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 3e5+5;
const int INF = 1e9+7;
const int mod = 998244353;

int n, m, T;
int siz[MAXN], cnt[MAXN], fa[MAXN];
bool flag[MAXN];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void Clear() {
	for(int i = 1; i <= m; ++i) cnt[i] = 1, fa[i] = i, siz[i] = flag[i] = 0;
}

signed main()
{
	T = read();
	while(T--) {
	    n = read(), m = read();
	    Clear();
	    for(int i = 1, u, v; i <= n; ++i) {
	        u = read(), v = read();
	        int uf = find(u), vf = find(v);
	        if(u == v) flag[uf] = true;
	        if(uf != vf) {
	            fa[uf] = vf;
	            flag[vf] |= flag[uf];
	            cnt[vf] += cnt[uf];
	            siz[vf] += siz[uf] + 1;
            } else {
                siz[vf] ++;
            }
        }
        int ans = 1;
        for(int i = 1; i <= m; ++i) {
            if(fa[i] == i) {
                if(siz[i] > cnt[i]) ans = ans * 0 % mod;
                else if(siz[i] == cnt[i]) {
                    if(flag[i]) ans = ans * 1 % mod;
                    else ans = ans * 2 % mod;
                } else {
                    ans = ans * cnt[i] % mod;
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

T3 - puzzle

这个题解和代码都是 std 给的,有没有能看懂的神仙来交一下 /kel

我们不妨令集合 \(U = \{ 1,2,...,k \}\),定义集合 \(A_i\) 为能放在第 \(i\) 行的数,且 \(A_i \subseteq U\),我们发现集合 \(\complement_U A_i\) 为能放在第 \(i\) 列的数。

现在要求 \(\forall i \not = j\),都有 $A_i \cap \complement_U A_j \not = \varnothing $,即 \(\forall i \not = j\),都有 \(A_i \nsubseteq A_j\) 。

所以我们现在要找到 \(n\) 个 \(U\) 的子集使得两两不互相包含。

当每个集合都包含相同个数的元素时,不会产生包含。那么当每个集合恰好有 \(\frac{k}{2}\) 个元素时,可以最大
化互相不包含的集合个数,这时集合个数为 \(\displaystyle\binom{k}{ \lfloor \frac{k}{2} \rfloor}\)

所以我们只要找到最小的 k 满足 \(\displaystyle\binom{k}{ \lfloor \frac{k}{2} \rfloor} \ge n\) 之后我们找到所有包含 \(\frac{k}{2}\) 个元素的 \(U\) 子集,并将这些子集安排到每一行中,最后输出答案即可。

#include <bits/stdc++.h>
#define REP(i,x,y) for(int i=(int)x;i<=(int)y;i++)
#define PER(i,x,y) for(int i=(int)x;i>=(iny)y;i--)
#define FOR(i,x,y) for(int i=(int)x;i< (int)y;i++)
#define fi first
#define se second
#define pb push_back
#define mk make_pair
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI>  VII;
int C[21][21],n,T,i,f[510],cnt[1<<13],lg[1<<13],t,j; 
int trans(int x,int y){
	for(x--;x;x--){
		for(;cnt[x] > y;x -= x & -x);
		if(cnt[x] == y)return x;
	}
} 
int main(){
	scanf("%d",&T);
	for(int i = 0; i <= 20; i++)
		for(int j = 0; j <= 20; j++)
			C[i][j] = i && j ? C[i - 1][j] + C[i][j - 1] : 1;
	for(int i = 0;i < 13;i++)lg[1<<i]= i + 1; 
	for(int i = 0; i < 1 << 13; i++)
		cnt[i] = cnt[i >> 1] + (i & 1); 
	while(T--){
		memset(f,0,sizeof(f));
		scanf("%d", &n);
		for(i = 2; C[i >> 1][i + 1 >> 1] < n; i++); 
		for(int j = trans(1 << i, i>>1), k = 1; k <= n; j = trans(j, i >> 1), k++)
			f[k] = j; 
		for(i=1;i<=n;i++,puts("")) 
			for(j=1;j<=n;j++)
				t=f[i] & (~f[j]), 
				printf("%d ", lg[t & -t]);
		 
	}
	return 0;
}

这题是 Special Judge,虽然我不会这题,但我通过它学会了 洛谷 SPJ 的写法,这还是很好的。

粘一个 SPJ:

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

int a[510][510], x;

int main(int argc, char **argv) {
	registerTestlibCmd(argc, argv);
	int T, n, Ans, mx;
    T = inf.readInt();
    while(T--){
    	n = inf.readInt();
    	Ans = mx = 0;
    	for(int i = 1; i <= n; i++)
    		for(int j = 1; j <= n; j++){
    			a[i][j] = ouf.readInt();
    			if(a[i][j] < 0 || (a[i][j] == 0 && i != j)) return quitf(_wa, "This matrix is illegal"), 0;
    			x = ans.readInt();
    			mx = max(mx, a[i][j]);
    			Ans = max(Ans, x);
    		}
    	if(mx != Ans) return quitf(_wa, "Your 'k' is big !"), 0;
    	for(int i = 1; i <= n; i++)
    		for(int j = 1; j <= n; j++) if(j != i)
    			for(int k = 1; k <= n; k++) if(k != i)
    				if(a[i][j] == a[k][i]) return quitf(_wa, "This matrix is illegal"), 0;
	}
	return quitf(_ok, "OK, You have Accepted it!"), 0;
}
上一篇:April Fools Day Contest 2021


下一篇:C[9] typedef 类型别名