hdu 7131 (DP)
用dp[i][j]表示文本串的前i个字符里面，有多少种方案能匹配模式串的前j个位
转移方程
dp[i][j] = dp[i - 1][j]
如果模式串第j位与文本串第i位匹配
dp[i][j] += dp[i-1][j-1]
初始化为dp[0~n][0] = 1
表示文本串为0到n时，与空串都有一个匹配，注意包括0
统计答案的话
每次成功匹配且匹配完成的时候
加上dp[i-1][j-1] * (pow(2, sum[i + 1]) - 1)
sum[i+1]是a的个数的后缀和
两个细节
1.字符串用char数组 从1开始好处理很多
2.涉及取模可以直接开long long 不用考虑哪些地方会爆int等等
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e5 + 10;
const int mod = 998244353;int cnt[N][15], sum[N];
char t[] = " nunhehheh";
ll fac[N], ans;
char s[N];int main()
{fac[0] = 1;_for(i, 1, 1e5) fac[i] = fac[i - 1] * 2 % mod;int T; scanf("%d", &T);while(T--){scanf("%s", s + 1);int len = strlen(s + 1);sum[len + 1] = 0;for(int i = len; i >= 1; i--)sum[i] = (s[i] == 'a') + sum[i + 1];ans = 0;memset(cnt, 0, sizeof cnt);_for(i, 0, len) cnt[i][0] = 1;_for(i, 1, len)_for(j, 1, 9){cnt[i][j] = cnt[i - 1][j];if(s[i] == t[j]){if(j == 9) ans = (ans + cnt[i - 1][j - 1] * (fac[sum[i + 1]] - 1)) % mod;cnt[i][j] = (cnt[i][j] + cnt[i - 1][j - 1]) % mod;}}if(ans < 0) ans += mod;printf("%lld\n", ans);}return 0;
}hdu 7130（数学）
需要推一下式子，难点在于转化
si + kT = x
两边同时模T
si % T = x % T
这是一个必要不充分条件
注意这里的k要大于等于0，这个直接模的过程中这个信息丢失了
我们换一种方式，两边加上若干个T，使得落在[0, T-1]这个区间内
即si + k1T = x + k2T
此时k1 - k2 >=0 即k1 >= k2
可以发现k1是可以预处理的，k2可以算出来，且只用算一次
为了使操作次数最小 需要找到一个最小的k1满足条件，k1相同的时候编号尽量小
于是可以预处理一下，以si % T为下标，加入(k1, i)
可以用map离散化一下赋个编号，然后存到vector里面，排个序
先取模来满足必要条件，然后用k1 >= k2从而满足条件，然后二分找最优
在vector里面二分就可以了
注意可能T为0，我因为这个RE了一次 要特判
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e5 + 10;
unordered_map<ll, int> id, ans;
vector<pair<ll, int>> ve[N];
int n, m, cnt;
ll a[N], c;ll cal(ll x)
{ll t = (x % c + c) % c;return (t - x) / a[n];
}int main()
{int T; scanf("%d", &T);while(T--){id.clear();cnt = 0;scanf("%d%d", &n, &m);_for(i, 1, n){scanf("%lld", &a[i]);a[i] += a[i - 1];}c = abs(a[n]);if(c == 0){ans.clear();_for(i, 1, n) if(!ans[a[i]])ans[a[i]] = i;while(m--){ll x; scanf("%lld", &x);if(x == 0) {puts("0");continue;}if(!ans[x]) puts("-1");else printf("%d\n", ans[x]);}continue;}_for(i, 1, n){ll cur = (a[i] % c + c) % c;if(!id[cur]) id[cur] = ++cnt;ve[id[cur]].push_back(make_pair(cal(a[i]), i));}_for(i, 1, cnt) sort(ve[i].begin(), ve[i].end());while(m--){ll x; scanf("%lld", &x);if(x == 0) {puts("0");continue;}ll k = cal(x);x = (x % c + c) % c;if(!id[x]) {puts("-1");continue;}int cur = id[x];int ans = lower_bound(ve[cur].begin(), ve[cur].end(), make_pair(k, 0)) - ve[cur].begin();if(ans == ve[cur].size()) puts("-1");else printf("%lld\n", ve[cur][ans].second + (ve[cur][ans].first - k) * n);}_for(i, 1, cnt) ve[i].clear();}return 0;
}
还有一种写法，不用一个map来过渡
直接stl套stl
unordered_map<ll, vector<pair<ll, int>>> mp;一开始WA了
发现是auto的时候没有引用 血的教训 好习惯 auto加上引用
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 1e5 + 10;
unordered_map<ll, vector<pair<ll, int>>> mp;
ll a[N], c;
int n, m;ll cal(ll x)
{ll t = (x % c + c) % c;return (t - x) / a[n];
}int main()
{int T; scanf("%d", &T);while(T--){mp.clear();scanf("%d%d", &n, &m);_for(i, 1, n){scanf("%lld", &a[i]);a[i] += a[i - 1];}c = abs(a[n]);if(c == 0){unordered_map<ll, int> ans;_for(i, 1, n) if(!ans[a[i]])ans[a[i]] = i;while(m--){ll x; scanf("%lld", &x);if(x == 0) {puts("0");continue;}if(!ans[x]) puts("-1");else printf("%d\n", ans[x]);}continue;}_for(i, 1, n){ll cur = (a[i] % c + c) % c;mp[cur].push_back(make_pair(cal(a[i]), i));}for(auto& x: mp) sort(x.second.begin(), x.second.end());while(m--){ll x; scanf("%lld", &x);if(x == 0) {puts("0");continue;}ll k = cal(x);x = (x % c + c) % c;if(mp[x].size() == 0) {puts("-1");continue;}int ans = lower_bound(mp[x].begin(), mp[x].end(), make_pair(k, 0)) - mp[x].begin();if(ans == mp[x].size()) puts("-1");else printf("%lld\n", mp[x][ans].second + (mp[x][ans].first - k) * n);}}return 0;
}
hdu 7135（图论）
这题很快就发现了如果形成一个2 * n的环，就可以满足条件
可以发现如果形成环，那么每个左边的点就有两条边相连
要字典序最小，就可以直接贪心
后来发现直接贪心的话会提早成环，也就是成了多个小环
为了避免这种情况，需要用并查集判断一下。最后左边的最后一个点连一条边成环
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
int f[N << 1], cnt[N][2], n, m;int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }void Union(int x, int y)
{f[find(x)] = find(y);
}int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);_for(i, 1, 2 * n) f[i] = i;memset(cnt, 0, sizeof cnt);_for(t, 1, m){int u, v;scanf("%d%d", &u, &v);Union(u, v + n);cnt[u][0]++; cnt[v][1]++;}printf("%d\n", 2 * n - m);_for(i, 1, n)while(cnt[i][0] < 2){_for(j, 1, n)if(cnt[j][1] < 2 && (i == n || find(i) != find(j + n))){printf("%d %d\n", i, j);cnt[i][0]++; cnt[j][1]++;Union(i, j + n);break;}}}return 0;
}
E. Tree Shuffling（贪心+dfs序+线段树）
我自己想了要给解法，和正解不太一样，之后再学一学正解
首先要进行交换的点数是一定的，那么可以贪心，也就是便宜的操作次数越多越好
所以我们可以按照花费的价值来把点排序，然后每次尽可能操作多的点
树形dp可以统计出子树内1 0 和0 1 的个数，然后来操作
操作完之后可以发现，当前点的子树的所有点都不用操作了，因为肯定是没有多余的点可以交换了，所以可以暴力把其子树都标记一下，之后遍历到这个点就可以跳过了。由于每个点只访问了一次，这个过程虽然暴力但是总的O（n）的
之后有一个问题，就是当前点操作后，会影响祖先的操作
也就是其所有祖先能成功交换的点都要减少
我在这卡了一下，不知道怎么操作
突然想到可以反过来，也就是在当前节点标记一下操作了数，然后每个点看能操作多少次的时候减去子树中已经操作过的次数
这个过程可以用dfs序 + 线段树来实现 单点修改区间查询
这道题就做完了，时间复杂度是O(nlogn)
#include <bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 2e5 + 10;
int t[N << 2], n;
int L[N], R[N], dp[N][2], vis[N], cnt;
vector<int> g[N];
struct node
{int a, id;
}s[N];void dfs(int u, int fa)
{L[u] = ++cnt;for(int v: g[u]){if(v == fa) continue;dfs(v, u);dp[u][1] += dp[v][1];dp[u][0] += dp[v][0];}R[u] = cnt;
}void up(int k)
{t[k] = t[l(k)] + t[r(k)];
}void add(int k, int l, int r, int x, int p)
{if(l == r){t[k] = p;return;}int m = l + r >> 1;if(x <= m) add(l(k), l, m, x, p);else add(r(k), m + 1, r, x, p);up(k);
}int query(int k, int l, int r, int L, int R)
{if(L <= l && r <= R) return t[k];int m = l + r >> 1, res = 0;if(L <= m) res += query(l(k), l, m, L, R);if(R > m) res += query(r(k), m + 1, r, L, R);return res;
}void mark(int u)
{vis[u] = 1;for(int v: g[u]){if(vis[v] || (L[v] <= L[u] && R[u] <= R[v])) continue;mark(v);}
}bool cmp(node x, node y)
{return x.a < y.a;
}int main()
{scanf("%d", &n);_for(i, 1, n){int x, y;scanf("%d%d%d", &s[i].a, &x, &y);if(x - y == 1) dp[i][0] = 1;if(x - y == -1) dp[i][1] = 1;s[i].id = i;}_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);sort(s + 1, s + n + 1, cmp);if(dp[1][0] != dp[1][1]){puts("-1");return 0;}ll ans = 0;_for(i, 1, n){int u = s[i].id, a = s[i].a;if(vis[u]) continue;int cost = min(dp[u][0], dp[u][1]) - query(1, 1, n, L[u], R[u]);ans += 2LL * cost * a;add(1, 1, n, L[u], cost);mark(u);}printf("%lld\n", ans);return 0;
}
D. Journey to Un'Goro（构造 + 搜索）
没想到这道构造题竟然是搜索
我一开始的思路就是打表找规律，结果没找出什么规律
没想到是爆搜加剪枝
首先是常见的思路转化为前缀和，区间和模一个数为奇数
直接模2，就相当于前缀和数组的值不同
也就是一对前缀和数组值不同就可以构成一个区间
如果有x个值为0的s数组，y个值为1的s数组
一对01或者10，可以全部看成先选1后选0
那么每次从x个中选一个1，从y中选一个0
那么就一定有xy对是符合条件的
那么要使得xy最大，显然x和y要尽可能靠近
s数组共有n + 1个位置（注意s[0]）
那么显然一个是除以2向下取整，一个向上取整
所以只要0和1的个数是一定的，就可以达到最大值
所以直接搜索加剪枝
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
char s[N];
int n, cnt;void dfs(int cnt0, int cnt1, int pos, int p)
{if(cnt == 100 || cnt0 > (n + 2) / 2 || cnt1 > (n + 2) / 2) return;if(pos == n + 1){printf("%s\n", s + 1);cnt++;return;}s[pos] = 'b';if(!p) dfs(cnt0 + 1, cnt1, pos + 1, p);else dfs(cnt0, cnt1 + 1, pos + 1, p);s[pos] = 'r';if(!p) dfs(cnt0, cnt1 + 1, pos + 1, p ^ 1);else dfs(cnt0 + 1, cnt1, pos + 1, p ^ 1);
}int main()
{scanf("%d", &n);printf("%lld\n", 1LL * ((n + 1) / 2) * ((n + 2) / 2));dfs(1, 0, 1, 0);return 0;
}
E. Tree Shuffling(贪心)
正解的思路挺巧妙的
我之前有一种想法就是一个点要被祖先中最小的点操作才最优
但不好实现，因为涉及到这个点和其他点交换
其实离正解很近了，正解就是考虑一个点什么时候操作其子树是最优的
那就是它的父亲节点花费都大于等于它的时候
所以我们可以dfs，维护出根节点到当前点的最小值，如果这个最小值等于当前点的值，那么当前点操作一定是最优的，这时操作就可以了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 2e5 + 10;
int dp[N][2], a[N], n;
vector<int> g[N];
ll ans;void dfs(int u, int fa, int mi)
{mi = min(mi, a[u]);for(int v: g[u]){if(v == fa) continue;dfs(v, u, mi);dp[u][0] += dp[v][0];dp[u][1] += dp[v][1];}if(mi == a[u]){int t = min(dp[u][0], dp[u][1]);ans += 2LL * t * a[u];dp[u][0] -= t;dp[u][1] -= t;}
}int main()
{scanf("%d", &n);_for(i, 1, n){int x, y;scanf("%d%d%d", &a[i], &x, &y);if(x - y == 1) dp[i][0] = 1;if(x - y == -1) dp[i][1] = 1;}_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0, 2e9);if(dp[1][0] != dp[1][1]) puts("-1");else printf("%lld\n", ans);return 0;
}C2. Not So Simple Polygon Embedding（计算几何+猜结论）
猜一下旋转的角度到中间的时候到最值就行了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int main()
{double pi = acos(-1);int T; scanf("%d", &T);while(T--){int n; scanf("%d", &n);if(n % 2 == 0) printf("%.10f\n", 1 / tan(pi / (2 * n)));else printf("%.10f\n", cos(pi / (4 * n)) / sin(pi / (2 * n)));}return 0;
}
D. Captain Flint and Treasure（逆向思维+图）
我的逆向思维要好好练一下，很多题都因为这个没有做出来
首先这道题是一个隐式的图
其实可以看作每一个节点有一个父亲，这样就变成了森林
我开始想有向无环图做拓扑排序
其实是麻烦了
这里面的点不可能有两个出边
所以这个DAG是比较特殊的，其实也就是森林
然后首先可以知道，如果值大于等于0，肯定越早越好，如果小于0，那就越小越好
这里的早晚其实就对应着深度
此外，这里可以分类讨论，输出的时候分大于等于0的输出和小于0的输出
是不影响的 是可以割裂开来的
对于大于等于0，先输出儿子再输出父亲，小于0，先父亲后儿子
在dfs递归的过程就包含了这个关系，可以保证子树先加入再加入根
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 2e6 + 10;
int b[N], n;
vector<int> g[N], po, ne;
ll a[N], ans;void dfs(int u, int fa)
{for(int v: g[u]){if(v == fa) continue;dfs(v, u);if(a[v] >= 0) a[u] += a[v];}if(a[u] >= 0) po.push_back(u);else ne.push_back(u);ans += a[u];
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%lld", &a[i]);_for(i, 1, n){scanf("%d", &b[i]);if(b[i] != -1) g[b[i]].push_back(i);}_for(i, 1, n)if(b[i] == -1)dfs(i, 0);printf("%lld\n", ans);for(int x: po) printf("%d ", x);for(int i = ne.size() - 1; i >= 0; i--) printf("%d ", ne[i]);return 0;
}B. Jzzhu and Cities（最短路 + 思维）
首先跑一遍最短路
怎么看一条路是一定不能删去的呢
也就是必须通过这条路才是最短路 不能通过其他的路
所以就是这条边的长度等于最短路且方案数为1
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 2e5 + 10;
int cnt[N], n, m, k;
struct node
{int v; ll w;bool operator < (const node& rhs) const{return w > rhs.w;}
};
vector<node> g[N];
ll d[N], mi[N];void solve()
{_for(i, 1, n) d[i] = 1e18;priority_queue<node> q;q.push(node{1, d[1] = 0});cnt[1] = 1;while(!q.empty()){node x = q.top(); q.pop();int u = x.v;if(x.w != d[u]) continue;for(auto t: g[u]){int v = t.v; ll w = t.w;if(d[v] > d[u] + w){d[v] = d[u] + w;q.push(node{v, d[v]});cnt[v] = cnt[u];}else if(d[v] == d[u] + w) cnt[v] += cnt[u];}}
}int main()
{scanf("%d%d%d", &n, &m, &k);while(m--){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].push_back(node{v, w});g[v].push_back(node{u, w});}_for(i, 1, n) mi[i] = 1e18;_for(i, 1, k){int s, y;scanf("%d%d", &s, &y);mi[s] = min(mi[s], (ll)y);}_for(i, 1, n)if(mi[i] != 1e18){g[1].push_back(node{i, mi[i]});g[i].push_back(node{1, mi[i]});}solve();int ans = 0;_for(i, 1, n)if(mi[i] == d[i] && cnt[i] == 1)ans++;printf("%d\n", k - ans);return 0;
}E. Directing Edges（拓扑排序判断环）
其实这题是一道比较裸的拓扑排序题
但是我遗忘了……
一个有向图可以用拓扑排序来判断是否有环
先忽略无向边，做一次拓扑排序
如果有环就一定不行
如果无环，那么那些无向边就可以按照拓扑排序的顺序选择方向
这样一定没有环，因为加了这些边依然满足拓扑排序的性质
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e5 + 10;
int degree[N], topo[N], n, m;
struct Edge { int t, u, v; };
vector<Edge> edge;
vector<int> g[N];int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);_for(i, 1, n) degree[i] = 0, g[i].clear(), topo[i] = 0;edge.clear();while(m--){int t, u, v;scanf("%d%d%d", &t, &u, &v);edge.push_back(Edge{t, u, v});if(t == 1) {degree[v]++;g[u].push_back(v);}}int id = 0;queue<int> q;_for(i, 1, n)if(!degree[i])q.push(i);while(!q.empty()){int u = q.front(); q.pop();topo[u] = ++id;for(int v: g[u])if(--degree[v] == 0)q.push(v);}bool ok = true;_for(i, 1, n)if(!topo[i]){ok = false;break;}if(!ok) puts("NO");else{puts("YES");for(auto x: edge){if(!x.t && topo[x.u] > topo[x.v]) swap(x.u, x.v);printf("%d %d\n", x.u, x.v);}}}return 0;
}D. Minimax Problem（二进制）
这题我很快就想到了二分答案加或运算
但是感觉判断是n方的，就不知道了
但是我没意识到的是
8位二进制的数就那么多，其实很多是重复的
所以当位数比较小的时候，数的个数是很有限的
此外注意一点
这个二分不太一样，检查答案的时候要记录一些值
所以一开始初始化的时候要记录答案，不然会WA，看代码
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 3e5 + 10;
int a[N][10], b[N], vis[N], ans1, ans2, n, m;
vector<pair<int, int>> ve;bool check(int key)
{ve.clear();rep(i, 0, 1 << m) vis[i] = 0;_for(i, 1, n){int cur = 0;_for(j, 1, m){cur <<= 1;if(a[i][j] >= key) cur++;}if(!vis[cur]) {ve.push_back(make_pair(cur, i));vis[cur] = 1;}}rep(i, 0, ve.size())_for(j, 0, i)if((ve[i].first | ve[j].first) == ((1 << m) - 1)){ans1 = ve[i].second;ans2 = ve[j].second;return true;}return false;
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, n)_for(j, 1, m)scanf("%d", &a[i][j]);int l = 0, r = 1e9 + 1;check(l); //细节！！！while(l + 1 < r){int m = l + r >> 1;if(check(m)) l = m;else r = m;}printf("%d %d\n", ans1, ans2);return 0;
}C. Omkar and Determination(细节)
最后十分钟 突然想到解法，写了一波，结果因为一个小错误WA了
可以发现只要有N的直角三角形就不行
如果上面和左边都是X就会存在这个三角形
所以判断一下就可以了
这里给的是nm，所以我用了string
结果我没注意直接从1开始循环，这样会访问到0
以往是空的是没有问题的
但是这道题而言，string这时是空的没有输入的，和char数组不一样
所以直接访问到非法的空间
所以应该改成从2开始循环
这个小细节倒是第一次碰到，因为这个很小的细节少了一道题……
另外不要放弃，我是最后十分钟突然有思路的，要坚持到最后
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e6 + 10;
int sum[N], n, m, q;
string s[N];int main()
{scanf("%d%d", &n, &m);_for(i, 1, n) {cin >> s[i];s[i] = " " + s[i];}_for(i, 2, n)_for(j, 2, m)if(s[i - 1][j] == 'X' && s[i][j - 1] == 'X')sum[j - 1] = 1;_for(i, 1, m) sum[i] += sum[i - 1];scanf("%d", &q);while(q--){int l, r;scanf("%d%d", &l, &r);puts(sum[r - 1] - sum[l - 1] ? "NO" : "YES");}return 0;
}