三道思维题，考场上我真是一道也不会啊
T1 装饰大楼：https://www.luogu.org/problem/T92137
失误：脑子貌似压根没转，没认真考虑怎么判重，乱写了个哈希还挂了...
考虑位于位置i，前面的最大值是k，那么这个位置可以填1-k+1
判重：如果a[i+1]值在[1,k+1]，那么会有一种重复情况，ans--即可
无解：1.前面是1-k，这里出现k+3及以上
2.有两个位置出现k+2
特殊的，当只有一个位置pos出现k+2时，我们只能在1-pos-1填入一个大小为k+1的数，且填入位置之前最大值必须为k
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<climits> #include<map> #include<queue> using namespace std; #define O(x) cout << #x << " " << x << endl; #define B cout << "breakpoint" << endl; #define clr(a) memset(a,0,sizeof(a)); #define int long long typedef long long ll; inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } const int maxn = 1e6 + 5; int n,a[maxn],ans; main() { freopen("A.in","r",stdin); freopen("A.out","w",stdout); n = read(); n--; for(int i = 1;i <= n;i++) a[i] = read(); int mx = 0; int pos = 0; for(int i = 1;i <= n;i++) { if(a[i] > mx + 2) { printf("0 "); return 0; } else if(a[i] == mx + 2) { if(pos) { printf("0 "); return 0; } pos = a[i]; } mx = max(mx,a[i]); } mx = 0; for(int i = 0;i <= n;i++) { mx = max(mx,a[i]); if(pos) { if(mx == pos - 2) ans++; continue; } ans += mx + 1; if(a[i + 1] <= mx + 1 && a[i + 1] > 0) ans--; } printf("%lld",ans); }
T2：https://www.luogu.org/problem/T92119
将所有端点拿出来，排序后离散化
对于相邻两个点，可以根据进出情况分为四种
将一种依赖的情况连边，dfs获得新的序列
f[i][j][0]/[1]表示前i个点，带j把钥匙，第i个人带或不带的最大答案
O（n^2）
依旧是没有思考...
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<climits> #include<map> #include<queue> using namespace std; #define O(x) cout << #x << " " << x << endl; #define B cout << "breakpoint" << endl; #define clr(a) memset(a,0,sizeof(a)); #define int long long typedef long long ll; const ll inf = LONG_LONG_MAX - 10; inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } const int maxn = 2005; struct node { int x,id; bool in,out; bool operator < (const node &b) const { return x < b.x; } }a[maxn << 1]; int n,tot,m,k,ans; int to[maxn],p[maxn],g[maxn],f[maxn][maxn][2],in[maxn]; int t[maxn],cnt; bool vis[maxn]; void dfs(int u) { if(!u) return; in[u] = 1; t[++cnt] = u; dfs(to[u]); } main() { freopen("B.in","r",stdin); freopen("B.out","w",stdout); n = read(),m = read(),k = read(); for(int i = 1;i <= n;i++) { a[++tot].x = read(),a[tot].id = i,a[tot].out = 1,a[tot].in = 0; a[++tot].x = read(),a[tot].id = i,a[tot].in = 1,a[tot].out = 0; } sort(a + 1,a + 1 + n * 2); ans += a[1].x + m - a[n * 2].x; for(int i = 1;i <= n * 2 - 1;i++) { int x1 = a[i].id,x2 = a[i + 1].id; int tp = a[i + 1].x - a[i].x; if(a[i].in && a[i + 1].out) ans += tp;//3 if(a[i].in && a[i + 1].in) p[x2] += tp;//4 if(a[i].out && a[i + 1].out) p[x1] += tp;//1 if(a[i].out && a[i + 1].in) { if(x1 == x2) p[x1] += tp; else in[x2] = 1,g[x2] = tp,to[x1] = x2; } } for(int i = 1;i <= n;i++) if(!in[i]) dfs(i); for(int i = 0;i <= n;i++) for(int j = 0;j <= k;j++) f[i][j][0] = f[i][j][1] = -inf; f[0][0][0] = 0; for(int i = 1;i <= n;i++) { for(int j = 0;j <= k;j++) { f[i][j][0] = max(f[i - 1][j][0],f[i - 1][j][1]); if(j) f[i][j][1] = max(f[i - 1][j - 1][1] + g[t[i]],f[i - 1][j - 1][0]) + p[t[i]]; } } printf("%lld",ans + max(f[n][k][1],f[n][k][0])); }
T3：咕