期望得分：\(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;
}