总结
期望：100 + 100 + 30 = 230
得分：100 + 80 + 30 = 210
zhx 的题，题目整体偏水
(T2) 特判没判全，挂了 (20) 分
(T3) 的 (dp) 好显然，考场上只顾着推结论，还没推出来，菜死了，菜死了 = =
为啥我每次考试写 T3 BS 和 szt 都在看小说，大雾 = =
T1 url
solution
先把字符串按长度从小到大排序
然后依次赋值 (a, b, c, d, e, f, g........)
这个东西可以打表打出来。
要处理出前 1000 个就够了。
数据范围很小，可以随便搞
code
#include<bits/stdc++.h>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n, tot = 1;
string mp[3000], s;
string b[1010], Ans[1010];
map<string, bool>fag;
map<string, string>c;
int num[3];
void dfs(int x, int goal) {
if(tot > 1005) return ;
if(x == goal + 1) {
for (int i = 1; i <= goal; i++) {
int x = num[i];
s = x + 'a' - 1;
mp[tot] = mp[tot] + s;
}
tot++;
return ;
}
for (int i = 1; i <= 26; i++) {
num[x] = i;
dfs(x + 1, goal);
}
}
struct node{
string s;
int id;
bool operator < (const node &rhs)const{
return s.length() < rhs.s.length();
}
}a[5010];
bool vis[5000];
int main() {
//freopen("url.in", "r", stdin);
//freopen("url.out", "w", stdout);
n = read();
for (int i = 1; i <= n; i++) {
cin>>a[i].s;
a[i].id = i;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= 3; i++) dfs(1, i);
for (int i = 1; i <= n; i++) {
if(fag[a[i].s] == 1) Ans[a[i].id] = c[a[i].s];
else {
for (int j = 1; j <= 2000; j++) {
if(vis[j]) continue;
if(mp[j] == a[i].s || mp[j].length() >= a[i].s.length()) continue;
vis[j] = 1;
Ans[a[i].id] = mp[j];
fag[a[i].s] = 1, c[a[i].s] = mp[j];
break;
}
}
}
for (int i = 1; i <= n; i++) cout<<Ans[i]<<"
";
return 0;
}
T2 异构体
solution
如果有入度大于 1 的点，就把连向该点的边取一个编号最大的一个
如果都为 1， 那就取环上编号最大的一个。
Tarjan 判环板子题 ？
无环：
取入度 > 1 的点，把连向它的边编号最大的一个边删掉。
有环：
没有入度为 0 的点，就从环上找一个编号最大的边的删掉
如果有入度为 0 的点，就找出环上入度为 2 的点，并把连向该点的一条在环上的边删掉。
code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n, from[MAXN], to[MAXN];
struct edge{int v, nxt;}e[MAXN << 1 + 5];
int E, head[MAXN];
void add_edge(int u, int v){
e[++E] = (edge){v, head[u]};
head[u] = E;
}
int ind[MAXN], Max[MAXN], tot, sc, dis[MAXN], siz[MAXN];
int dfn[MAXN], low[MAXN], vis[MAXN];
stack<int>s;
map<int, bool>link[MAXN];
void Tarjan(int x) {
s.push(x), vis[x] = 1;
low[x] = dfn[x] = ++tot;
for (int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if(!dfn[v]) {
Tarjan(v);
low[x] = min(low[x], low[v]);
}
else if(vis[v]) low[x] = min(low[x], dfn[v]);
}
int k, lst = x;
if(low[x] == dfn[x]) {
do{
k = s.top(), vis[k] = 0;
s.pop();
link[k][lst] = 1;
lst = k;
if(k == x) break;
dis[x] = max(dis[x], dis[k]);
siz[x]++;
}while(1);
}
}
int fag, id, tag;
int main() {
//freopen("remove.in", "r", stdin);
//freopen("remove.out", "w", stdout);
n = read();
for (int i = 1; i <= n; i++) {
int u = read(), v = read();
Max[v] = max(Max[v], i);
from[i] = u, to[i] = v;
ind[v]++, dis[v] = i;
add_edge(u, v);
siz[i] = 1;
}
for (int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i);
for (int i = 1; i <= n; i++) {
if(!ind[i]) fag = 1;
if(ind[i] == 2) id = i;
}
for (int i = 1; i <= n; i++) {
if(siz[i] == 1) tag++;
}
if(tag == n) {
cout<<Max[id];
return 0;
}
if(fag) {
for (int i = n; i >= 1; i--) {
if(link[from[i]][to[i]] && to[i] == id) {
cout<<i;
return 0;
}
}
}
for (int i = 1; i <= n; i++) {
if(siz[i] > 1) {
cout<<dis[i];
return 0;
}
}
puts("");
return 0;
}
T3 给大佬递茶
solution
一个模拟题意的 (dp)
设 (f_{i, j}) 表示第一个人剩下 (i) 吨茶，第二个人剩下 (j) 杯茶的概率。
转移就枚举倒多少就好了。
(f_{i - a_i, j - (4k - a_i)} += f_{i, j} / 4)
复杂度 (O(n^2))
有个结论 (Ans(n, k) = Ans(ceil(n / k), k))
然后你打个表会发现，当 (n) 很大，并且 (k = 1) 的时候，输出都是 (1) 。
后面的情况都可以转换到 (k = 1) 的情况。
code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n, k, a[5];
double f[MAXN][MAXN];
int main() {
n = read(), k = read();
n = (n - 1) / k + 1, k = 1;
if(n <= 1000) {
a[1] = k, a[2] = 2 * k, a[3] = 3 * k, a[4] = 4 * k;
f[n][n] = 1;
for (int i = n; i >= 0; i--) {
for (int j = n; j >= 0; j--) {
if(i == 0 || j == 0) continue;
for (int w = 1; w <= 4; w++) {
f[max(0, i - a[w])][max(0, j - (4 * k - a[w]))] += f[i][j] / 4.0;
}
}
}
double ret_1 = 0, ret_2 = f[0][0] / 2.0;
for (int i = 1; i <= n; i++) ret_1 += f[0][i];
printf("%.6lf", ret_1 + ret_2);
}
else puts("1.000000");
return 0;
}