最近做的一场比赛，把自己负责过的题目记一下好了。
Problem B URAL 2013 Neither shaken nor stirred
题意：一个有向图，每个结点一个非负值，可以转移到其他结点。初始时刻从结点出发，然后每次到达一个结点询问上一个到达的正值结点的权值，离开结点时也要询问一下，因为当前结点可能为正数，答案就是这个值了，如果不存在这个样的正权值输出“sober",或者不明确时输出“unkonwn”。
分析：可以当做树形dp来做。dp[u][0]表示进入结点时上一个正权值，dp[u][1]表示离开结点时的正权值, val[u]表示结点u权值,inf表示不明确情况。
转移这样来做：
对于边u->v，首先考虑dp[v][1]， val[v] != 0时， dp[v][1] = val[v]，否则dp[v][1] = dp[v][0]。
如果v没有访问过,dp[v][0] = dp[u][1]， v访问过，那么dp[v][0] != dp[u][1]时，更新dp[v][0] = inf，并且 当val[v] = 0时，要从v点重新出发dfs， 因为此时dp[v][1]值也会变化。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-8
#define lowbit(x) ((x)&(-x))
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define out freopen("solve_out.txt", "w", stdout); #define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef map<int, int> MPS;
const int maxn = + ;
vector<int> g[maxn];
int vis[maxn];
int dp[maxn][], val[maxn];
void dfs(int u, int fa) {
if(vis[u]) {
if(dp[fa][] != dp[u][]) {
dp[u][] = inf;
if(!val[u]) {
dp[u][] = inf;
for(int i = ; i < sz(g[u]); i++) {
int v = g[u][i];
dfs(v, u);
}
}
}
return;
}
vis[u] = ;
dp[u][] = dp[fa][];
dp[u][] = val[u] ? val[u] : dp[u][];
for(int i = ; i < sz(g[u]); i++) {
int v = g[u][i];
dfs(v, u);
}
}
int main() { int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
int m;
scanf("%d%d", &val[i], &m);
for(int j = ; j < m; j++) {
int u;
scanf("%d", &u);
g[i].pb(u);
}
}
vis[] = ;
dp[][] = ;
dp[][] = val[] ? val[] : ;
for(int i = ; i < sz(g[]); i++) {
int u = g[][i];
dfs(u, );
}
for(int i = ; i <= n; i++) {
if(dp[i][] == )
cout << "sober ";
else if(dp[i][] == inf)
cout << "unknown ";
else cout << dp[i][] << ' ';
if(dp[i][] == )
cout << "sober\n";
else if(dp[i][] == inf)
cout << "unknown\n";
else cout << dp[i][] << endl;
}
return ;
}
Problem C URAL 2014 Zhenya moves from parents
题意：共有n张收支凭据，根据当前的收到的凭据算出账户欠款，当前不足支出时，从账户扣除，收到一笔钱时把钱拿在手上不会去还信用卡上的钱，所以
信用卡欠款会越来越多的。
将时间离散化，排个序，然后以此建立线段树，每次将凭据对应的金额插入更新。线段树两个节点值，dep[rt]，表示当前区间时账户欠款，tot[rt]表示当前区间时能够剩下的现金。具体更新：
dep[rt] = dep[rt<<1] + min(0LL, tot[rt<<1]+dep[rt<<1|1]);
tot[rt] = tot[rt<<1|1] + max(tot[rt<<1]+dep[rt<<1|1], 0LL);
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-8
#define lowbit(x) ((x)&(-x))
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define out freopen("solve_out.txt", "w", stdout); #define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef map<string, int> MPS;
const int maxn = + ; struct Node {
int mon, day, h, mi, c, id;
Node() {}
Node(int mon, int day, int h, int mi, int c, int id):mon(mon), day(day), h(h), mi(mi), c(c), id(id) {}
bool operator < (const Node &o)const {
if(mon == o.mon) {
if(day == o.day) {
if(h == o.h) return mi < o.mi;
return h < o.h;
}
return day < o.day;
}
return mon < o.mon;
}
} b[maxn];
int a[maxn];
char s[];
int pos[maxn];
LL dep[maxn<<], tot[maxn<<];
void PushUp(int rt) {
dep[rt] = dep[rt<<] + min(0LL, tot[rt<<]+dep[rt<<|]);
tot[rt] = tot[rt<<|] + max(tot[rt<<]+dep[rt<<|], 0LL);
}
void update(int l, int r, int rt, int p, int c) {
if(p == l && p == r) {
if(c > )
tot[rt] = c;
else dep[rt] = c;
return;
}
int m = (l+r)>>;
if(p <= m)
update(lson, p, c);
else update(rson, p, c);
PushUp(rt);
} int main() { int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
int c, day, mon, h, mi;
scanf("%d %d.%d %d:%d", &c, &day, &mon, &h, &mi);
b[i] = Node(mon, day, h, mi, c, i);
a[i] = c;
}
sort(b+, b+n+);
for(int i = ; i <= n; i++)
pos[b[i].id] = i;
for(int i = ; i <= n; i++) {
update(, n, , pos[i], a[i]);
LL ans = dep[];
printf("%I64d\n", ans);
}
return ;
}
Problem F URAL 2017 Best of a bad lot
题意：有n个人处在不同的位置，声称目击哪些人也在场，这些人中有一些是嫌疑人，但是他们为了洗脱嫌疑会让他们的证词不相互矛盾，而其他人则会说出真正的情况。问最小的嫌疑团体。
分析：2个人所在地方不同，但是都目击同一个人，那么这两个人必定有一个为嫌疑人，很显然可以建立一个二分图，每次给图中结点着色，选取最少的加入到答案中。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-8
#define lowbit(x) ((x)&(-x))
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define out freopen("solve_out.txt", "w", stdout); #define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef map<string, int> MPS; const int maxn = ;
typedef set<int> :: iterator IT; vector<int>g[maxn];
set<int> a[maxn];
vector<string> name; int vis[maxn];
vector<int> tmp[];
void dfs(int u, int col) {
tmp[col].pb(u);
vis[u] = ;
for(int i = ; i < sz(g[u]); i++) {
int v = g[u][i];
if(vis[v]) continue;
dfs(v, col^);
}
}
int main() { int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
string str;
cin >> str;
name.pb(str);
int m;
scanf("%d", &m);
for(int j = ; j < m; j++) {
int k;
scanf("%d", &k);
a[i].insert(k);
}
a[i].insert(i);
}
for(int i = ; i <= n; i++) {
for(int j = i+; j <= n; j++) {
if(name[i-] != name[j-]) {
for(IT it = a[i].begin(); it != a[i].end(); it++)
if(a[j].count(*it)) {
g[i].pb(j);
g[j].pb(i);
break;
}
}
}
}
vector<int> ans;
for(int i = ; i <= n; i++) {
if(vis[i] || sz(g[i]) == ) continue;
tmp[].clear();
tmp[].clear();
dfs(i, );
if(tmp[].size() > tmp[].size()) tmp[] = tmp[];
for(int j = ; j < sz(tmp[]); j++)
ans.pb(tmp[][j]);
}
if(sz(ans)) {
cout << sz(ans) << endl;
for(int i = ; i < ans.size(); i++)
printf("%d%c", ans[i], i == sz(ans)- ? '\n' : ' ');
} else {
puts("");
puts("");
}
return ;
}
Problem G URAL 2018 The Debut Album
题意：每个元素可以为1,或2，组成n个元素的排列，且连续1的个数不能超过a，连续2的个数不能超过b问有多少种方式.
分析：dp[now][0][len],表示当前位为1，前面已经有len个连续1了，
转移：dp[now][0][len] = dp[pre][0][len-1],len > 1
dp[now][0][len] = sum{dp[pre][1][k]| 1 <= k <= b},len == 1
当前位为0时同理。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-8
#define lowbit(x) ((x)&(-x))
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define out freopen("solve_out.txt", "w", stdout); #define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef map<int, int> MPS;
const int maxn = + ;
const int M = (int)1e9 + ;
LL dp[][][];
int main() { int n, a, b;
scanf("%d%d%d", &n, &a, &b);
dp[][][] = dp[][][] = ;
for(int i = ; i <= n; i++) {
int now = i&;
int pre = ^now; for(int j = ; j <= a; j++) {
dp[now][][j] = ;
if(j == ) {
for(int k = ; k <= b; k++)
dp[now][][j] = (dp[now][][j] + dp[pre][][k])%M;
} else
dp[now][][j] = (dp[now][][j] + dp[pre][][j-])%M;
}
for(int j = ; j <= b; j++) {
dp[now][][j] = ;
if(j == ) {
for(int k = ; k <= a; k++)
dp[now][][j] = (dp[now][][j] + dp[pre][][k])%M;
} else
dp[now][][j] = (dp[now][][j] + dp[pre][][j-])%M;
}
}
LL ans = ;
int now = n&;
for(int i = ; i <= a; i++)
ans = (ans + dp[now][][i])%M;
for(int i = ; i <= b; i++)
ans = (ans + dp[now][][i])%M;
cout << ans << endl;
return ;
}
Problem H URAL 2019 Pair: normal and paranormal
题意：括号匹配
分析：多重括号匹配，每种字母代表一个，A只能和a匹配。
代码：
Problem J URAL 2021 Scarily interesting!
题意：安排两个队伍n场比赛的得分，使得悬念保持的越长越好。
分析：赢的那方从小到大，另一方从大到小。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-8
#define lowbit(x) ((x)&(-x))
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define out freopen("solve_out.txt", "w", stdout); #define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef map<int, int> MPS;
const int maxn = ;
int a[maxn], b[maxn], r1[maxn], r2[maxn];
bool cmp1(int x, int y) {
return a[x] > a[y];
}
bool cmp2(int x, int y) {
return b[x] > b[y];
}
int main() { int n;
scanf("%d", &n);
int sum1 = , sum2 = ;
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
sum1 += a[i];
r1[i] = i;
}
for(int i = ; i <= n; i++) {
scanf("%d", b+i);
sum2 += b[i];
r2[i] = i;
}
sort(r1+, r1+n+, cmp1);
sort(r2+, r2+n+, cmp2);
if(sum1 > sum2) {
for(int i = ; i <= n; i++)
printf("%d %d\n", r1[n+-i], r2[i]);
} else if(sum1 < sum2) {
for(int i = ; i <= n; i++)
printf("%d %d\n", r1[i], r2[n+-i]);
} else {
for(int i = ; i <= n; i++)
printf("%d %d\n", i, i);
}
return ;
}