(sf E-Shiritori)
博主的 ( m bibi) 时间
“怎么会有人连 ( m abc) 都不会做啊？”
解法
设每个串前三位为 (u)，后三位为 (v)。
先开始想的是从 (u) 向 (v) 连边，但是判 Draw 即判环会很难。因为环上某点可能有非 Draw 解。
反着建边就行了。
代码
#include <bits/stdc++.h>
using namespace std;
#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
const int maxn=4e5+5;
int n,len,idx,in[maxn],ans[maxn];
char s[maxn][10];
map <string,int> mp;
vector <int> e[maxn];
queue <int> q;
void Go() {
rep(i,1,idx) {
ans[i]=-1;
if(!in[i]) q.push(i),ans[i]=0;
}
while(!q.empty()) {
int t=q.front(); q.pop();
for(int i=0;i<e[t].size();++i) {
int v=e[t][i];
if(ans[v]==-1) {
--in[v];
if(!ans[t]) ans[v]=1,q.push(v);
else if(!in[v]) ans[v]=0,q.push(v);
}
}
}
}
int main() {
string u,v; int x,y;
n=read(9);
rep(i,1,n) {
scanf("%s",s[i]+1); len=strlen(s[i]+1);
u=""; u+=s[i][1];
u+=s[i][2],u+=s[i][3];
v=""; v+=s[i][len-2];
v+=s[i][len-1],v+=s[i][len];
if(!mp[u]) mp[u]=++idx;
if(!mp[v]) mp[v]=++idx;
x=mp[u],y=mp[v];
e[y].push_back(x); ++in[x];
}
Go();
rep(i,1,n) {
len=strlen(s[i]+1);
v=""; v+=s[i][len-2];
v+=s[i][len-1],v+=s[i][len];
y=mp[v];
if(ans[y]==-1) puts("Draw");
else if(ans[y]) puts("Aoki");
else puts("Takahashi");
}
return 0;
}
(sf F-Deforestation)
解法
尝试将问题简单化，先考虑树 (i) 和 (i+1)。
容易发现，这两棵树被砍的顺序并不影响除它们之外树的贡献。而先砍 (i) 贡献为 (h_i+2h_{i+1})，先砍 (i+1) 贡献为 (2h_i+h_{i+1})。
为了使花费最小化，我们应该先砍 (h_i,h_{i+1}) 中较高的一棵。
设 (dp_{i,j}) 为前 (i) 棵树，第 (i) 棵树是第 (j) 个被砍的砍伐排列数。
- (h_i=h_{i+1})。(dp_{i+1,j}=sum_{k=1}^{i}dp_{i,k})。相当于没有限制，但由于只砍了前 (i) 棵树，所以 (kle i)。
- (h_i>h_{i+1})。(dp_{i+1,j}=sum_{k=1}^{j-1} dp_{i,k})。
- (h_i<h_{i+1})。(dp_{i+1,j}=sum_{k=j}^i dp_{i,k})。取 (dp_{i,j}) 则是因为 (h_{i+1}) 本质上是插入进砍伐序列（位置固定），所以虽然此时 (h_i) 排在第 (j+1) 位，它实际只需统计 (j) 棵树。
用前缀和即可优化到 (mathcal O(n^2))。
另：自己在实现时将 < 打反了，但还是过了此题。其实 “矮优先” 和 “高优先” 是等价的，可以把砍伐序列倒过来看来理解。
代码
#include <bits/stdc++.h>
using namespace std;
#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
const int maxn=4005,mod=1e9+7;
int n,h[maxn],dp[2][maxn];
int main() {
n=read(9);
rep(i,1,n) h[i]=read(9);
dp[1][1]=1;
rep(i,2,n) rep(j,1,i) {
if(h[i]==h[i-1]) dp[i&1][j]=dp[i&1^1][i-1];
else if(h[i]<h[i-1]) dp[i&1][j]=dp[i&1^1][j-1];
else dp[i&1][j]=(dp[i&1^1][i-1]-dp[i&1^1][j-1]+mod)%mod;
dp[i&1][j]=(dp[i&1][j]+dp[i&1][j-1])%mod;
}
print(dp[n&1][n],'
');
return 0;
}