2018 ACM-ICPC南京网络赛
前言
去了一周秦皇岛回来就发生了鬼故事
离散讲完了……概率统计也讲完了……大物也讲完了……
才去一周啊怎么都讲完了 T^T
补作业补到死_(:з」∠)_
回来谈谈今年的南京网赛，感觉是被带偏榜了，线段树那道题目竟然没看到？？？？死磕不会做的题目？？？
菜是原罪！
这次写8题，其中好像有两三题之前写过了，直接copy，剩下的4题如果题解看得懂再说吧
还有最近太忙了，不能维持2-3天一篇的速度，各位见谅_(:з」∠)_
A - An Olympian Math Problem
题意
求sum(i -> n-1)(i * i!) % n 的值
思路 —— 打表
签到题，打表找规律，结果是 n - 1
#include <iostream>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
long long n;
cin >> n;
cout << n - 1 << endl;
}
}
L - Magical Girl Haze
题意
给定一幅图，求将K条边置为0后，从点1到点n的最短路的值
思路 —— 最短路 + 状压思想
借助状压DP的思想，在跑Dijkstra的时候在d数组上多开一维记录下在删除k条边时到达这一点的最短路的值，队列中也是多开一维记录下当前已经删除了k条边，再进入进入下一个点时，可以不删边进入，在当前还能继续删边时，还要再加入一个删边进入了的点
另外，在队列中让删边多的点先出队列能提高运行效率（不确定不这样做会不会TLE）
最后，答案是d[n][k]
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 3;
const int M = 2e5 + 3;
const ll inf = 1LL << 60;
struct edge{
int v, w, nxt;
};
struct Node{
int u;
ll w;
int k;
bool operator < (const Node& b) const{
if(w != b.w) return w > b.w;
else return k < b.k;
}
};
priority_queue<Node> que;
ll d[N][12];
edge e[M];
int head[N];
int tot;
inline int read(){
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
inline void init(){
memset(head, -1, sizeof(head));
tot = 0;
}
inline void addEdge(int u, int v, int w){
e[tot] = edge{v, w, head[u]};
head[u] = tot++;
}
ll dijkstra(int n, int lim){
while(!que.empty()) que.pop();
fill(d[0], d[N - 1] + 12, inf);
d[1][0] = 0;
que.push(Node{1, 0, 0});
while(!que.empty()){
Node nd = que.top();
que.pop();
int u = nd.u, w = nd.w, k = nd.k;
if(w > d[u][k]) continue;
if(u == n) return w;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(d[v][k] > d[u][k] + e[i].w){
d[v][k] = d[u][k] + e[i].w;
que.push(Node{v, d[v][k], k});
}
if(k + 1 <= lim && d[v][k + 1] > d[u][k]){
d[v][k + 1] = d[u][k];
que.push(Node{v, d[v][k + 1], k + 1});
}
}
}
return inf;
}
int main(){
int t = read();
while(t--){
int n = read(), m = read(), k = read();
init();
while(m--){
int u = read(), v = read(), w = read();
addEdge(u, v, w);
}
printf("%lld\n", dijkstra(n, k));
}
}
J - Sum
题意
定义一个数为square-free是该数无因数是平方数，定义f(i)为一个数i分解为两个数(a,b)且a和b都不是平方数的分解方案，这里(a,b)和(b,a)视为两种方案，求sum(f(i))
思路 —— 线性筛
可以知道f(i)是一个积性函数（可以打表观察出）
那么最后要解决的就是如何计算f(p^k)的问题
当k = 1时，f(p^k) = 2
当k = 2时，f(p^k) = 1
当k >= 3时，f(p^k) = 0
下面的代码差点TLE = =
#include <iostream>
#include <cstdio>
#include <list>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 2e7 + 5;
const int inf = 0x3f3f3f3f;
typedef long long ll;
ll f[N], sum[N];
bool isprime[N];
int prime[N], tot;
int cnt[N];
int quickPow(int a, int b){
int ans = 1, base = a;
while(b){
if(b&1) ans = ans * base;
base = base * base;
b >>= 1;
}
return ans;
}
void init(){
memset(isprime, true, sizeof(isprime));
tot = 0, f[1] = 1, sum[1] = 1;
for(int i = 2; i < N; i++){
if(isprime[i]){
prime[tot++] = i;
cnt[i]++;
}
for(int j = 0; j < tot && i * prime[j] < N; j++){
isprime[i * prime[j]] = false;
if(i % prime[j] == 0){
cnt[i * prime[j]] = cnt[i] + 1;
break;
}else{
cnt[i * prime[j]] = 1;
}
}
}
for(int i = 0; i < tot && (ll)prime[i] * prime[i] < N; i++){
f[prime[i] * prime[i]] = 1;
ll cur = (ll)prime[i] * prime[i] * prime[i];
while(cur < N){
f[cur] = 0;
cur = cur * prime[i];
}
}
for(int i = 2; i < N; i++){
if(isprime[i]){
f[i] = 2;
}
for(int j = 0; j < tot && i * prime[j] < N; j++){
if(i % prime[j] == 0){
int pk = quickPow(prime[j], cnt[i * prime[j]]);
f[i * prime[j]] = f[pk] * f[i * prime[j] / pk];
break;
}else{
f[i * prime[j]] = f[i] * f[prime[j]];
}
}
sum[i] = f[i] + sum[i - 1];
}
}
int main(){
init();
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
printf("%lld\n", sum[n]);
}
}
B - The writing on the wall
题意
给定一个 N * M 的充满 1 * 1 的格子的矩形，将多个给定的格子涂黑后，求不含黑格子的矩形总个数 (1 <= N <= 10^5, 1 <= M <= 100)
思路 —— 暴力
枚举每一个点作为矩形的右上点的情况，那么可以用O(n^3)的方法将矩形统计出来，具体方法是先双重循环枚举点作为右上点的情况，在往回扫描（即再套一层循环）动态维护每一列的黑格子出现在遍历过的哪一行，并不断更新可行的矩阵的高并滚动更新答案，观察到M最大只是100，因此可以选择O(N*M*M)的遍历方式完成以上的过程
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 15;
const int M = 100 + 15;
bool tag[N][M];
int p[N];
void init(int n, int m){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
tag[i][j] = false;
}
}
memset(p, 0, sizeof(p));
}
int main(){
int t, csn = 1;
scanf("%d", &t);
while(t--){
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
init(n, m);
while(k--){
int x, y;
scanf("%d%d", &x, &y);
tag[x][y] = true;
}
ll sum = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(tag[i][j]){
p[j] = i;
}
}
for(int j = 1; j <= m; j++){
int h = i;
for(int k = j; k >= 1; k--){
h = min(h, i - p[k]);
sum += h;
}
}
}
printf("Case #%d: %lld\n", csn++, sum);
}
}
E - AC Challenge
题意
给定N个任务，每个任务可能需要先完成前置任务，每个任务完成的得分是t*a[i]+b[i]，现在需要安排合理的任务完成顺序，使完成任务的总得分最大
思路 —— 状压DP
定义DP状态为完成哪些任务获得的得分最大值dp[st]，则dp[st] = max{dp[prest] + a[j]*getSt(st) + b[j]}，其中j为当前枚举的任务，prest = st ^ j，注意要处理一下st使其合法，所谓合法就是要满足前置任务的要求
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 20 + 1;
typedef long long ll;
const ll inf = 1LL << 60;
int a[N], b[N];
int lim[N];
int arrst[1 << N], pst;
bool ok[1 << N];
ll dp[1 << N];
void getSt(int n){
pst = 0;
memset(ok, false, sizeof(ok));
for(int st = 0; st < (1 << n); st++){
bool flag = true;
for(int j = 0; j < n; j++){
if((st & (1 << j)) && ((st & lim[j]) != lim[j])){
flag = false;
break;
}
}
if(flag){
arrst[pst++] = st;
ok[st] = true;
}
}
}
int getCnt(int x){
int cnt = 0;
while(x){
cnt++;
x -= (x & -x);
}
return cnt;
}
int main(){
int n;
while(~scanf("%d", &n)){
memset(dp, 0, sizeof(dp));
for(int i = 0; i < n; i++){
scanf("%d%d", &a[i], &b[i]);
lim[i] = 0;
int k;
scanf("%d", &k);
while(k--){
int tmp;
scanf("%d", &tmp);
lim[i] += (1 << (tmp - 1));
}
}
getSt(n);
ll ans = -inf;
for(int i = 0; i < pst; i++){
int st = arrst[i];
int cnt = getCnt(st);
for(int j = 0; j < n; j++){
if((st & (1 << j)) == 0) continue;
if(!ok[st^(1 << j)]) continue;
dp[st] = max(dp[st], dp[st^(1 << j)] + a[j]*cnt + b[j]);
ans = max(ans, dp[st]);
}
}
printf("%lld\n", ans);
}
}
G - Lpl and Energy-saving Lamps
题意
已知有N个房间，每个房间有k[i]个灯泡需要更换。现在每个月都买入 m 个灯泡，从编号小的房间开始换灯泡，如果其需要更换的数量超过现有数量，则跳过，直到找到第一个数量不超过现有数量的房间进行更换，如果更换后还有剩余则继续寻找，如果都不能更换则等到下一个月。现在给定q个询问，每个询问输出第d个月有多少个房间灯泡已经更换完毕，以及当前还有多少个灯泡
思路 —— 线段树单点更新
为什么比赛的时候没看到这道题 T^T
记当前灯泡数量为b，开线段树并直接枚举月份，循环询问比b小的数，若有则更新b，并将该房间灯泡设为inf，直到无跳出询问并保存已更换数量以及b，进入下一月份，最后对于询问只需要输出保存的结果即可
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int seg[N << 2], a[N];
int ans_room[N * 40], ans_lamp[N * 40];
void pushUp(int rt){ seg[rt] = min(seg[rt << 1], seg[rt << 1 | 1]); }
void build(int l, int r, int rt){
if(l == r){
seg[rt] = a[l];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushUp(rt);
}
int query(int val, int l, int r, int rt){
if(seg[rt] > val) return -1;
if(l == r) return l;
int m = (l + r) >> 1;
if(seg[rt << 1] <= val) return query(val, lson);
else return query(val, rson);
}
void update(int p, int l, int r, int rt){
if(l == r){
seg[rt] = inf;
return;
}
int m = (l + r) >> 1;
if(p <= m) update(p, lson);
else update(p, rson);
pushUp(rt);
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
ans_room[0] = ans_lamp[0] = 0;
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
build(1, n, 1);
int month = 1, lamp = m;
while(true){
if(seg[1] == inf) break;
int cnt = 0;
while(true){
int pos = query(lamp, 1, n, 1);
if(pos == -1) break;
lamp -= a[pos];
update(pos, 1, n, 1);
cnt++;
}
ans_room[month] = ans_room[month - 1] + cnt;
ans_lamp[month] = lamp;
month++;
lamp += m;
}
int q;
scanf("%d", &q);
while(q--){
int x;
scanf("%d", &x);
x = min(x, month - 1);
printf("%d %d\n", ans_room[x], ans_lamp[x]);
}
}
}
I - Skr
题意
求回文串转数字和
思路 —— 回文树
回文树模板题
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e6 + 5;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
typedef long long ll;
char s[N];
int powten[N];
void init(){
powten[0] = 1;
for(int i = 1; i < N; i++){
powten[i] = (ll)powten[i - 1] * 10 % MOD;
}
}
struct Node{
int slink, len, cnt;
int nxt[10];
};
struct PalindromicTree{
int tot;
int cursuffix;
Node tree[N];
int num[N];
void init(){
num[0] = num[1] = 0;
tree[0].slink = 0, tree[0].len = -1, tree[0].cnt = 1;
tree[1].slink = 0, tree[1].len = 0, tree[1].cnt = 1;
tot = 2, cursuffix = 1;
initNode(1);
initNode(0);
}
void initNode(int o){
memset(tree[o].nxt, -1, sizeof(tree[o].nxt));
}
ll add(int pos){
int idx = s[pos] - '0';
int cur = cursuffix;
while(true){
int curlen = tree[cur].len;
if(pos - 1 - curlen >= 0 && s[pos] == s[pos - 1 - curlen]) break;
cur = tree[cur].slink;
}
if(tree[cur].nxt[idx] != -1){
cursuffix = tree[cur].nxt[idx];
return 0;
}
int nxt = tree[cur].nxt[idx] = tot++;
initNode(nxt);
tree[nxt].len = tree[cur].len + 2;
tree[cur].nxt[idx] = nxt;
cursuffix = nxt;
if(tree[nxt].len == 1){
tree[nxt].cnt = 1;
tree[nxt].slink = 1;
return num[nxt] = s[pos] - '0';
}
num[nxt] = ((ll)num[cur] * 10 + (ll)(s[pos] - '0') * (powten[tree[nxt].len - 1] + 1)) % MOD;
while(true){
cur = tree[cur].slink;
int curlen = tree[cur].len;
if(pos - 1 - curlen >= 0 && s[pos] == s[pos - 1 - curlen]){
tree[nxt].slink = tree[cur].nxt[idx];
break;
}
}
return num[nxt];
}
};
PalindromicTree pt;
int main(){
init();
pt.init();
ll ans = 0;
scanf("%s", s);
for(int i = 0; s[i]; i++){
ans = (ans + pt.add(i)) % MOD;
}
printf("%lld\n", ans);
}
K - The Great Nim Game
题意
有N堆石子（N为大数），每堆的个数按给定公式生成，问去掉若干堆后进行Nim博弈，先手必胜的方式有多少种
思路 —— Nim博弈 + 快速幂 + 乘法逆元 + 线性基
首先是Nim博弈结论，异或和为0则必败，因此原题目的反面等价于求异或和为0的组合种数（记为b），答案则为2^n - b
异或和为0的组合种数可以用线性基求解。首先k最大只有4096，因此用公式求出的值的循环节最大也就4096，而构造线性基的话，循环节以外的数，都能被这一循环节的数异或得到0，因此对构造出来的线性基没有影响。知道了这一点，便可将可判定出现循环节为止的数拿去构造线性基，进而求出线性基的秩。以前写二进制那篇文章，里面有一个结论“异或得到的数重复2^(n-|B|)次”，这里的|B|是线性基的秩，因此0也会出现这么多次，于是我们需要得到的答案就是2^n - 2^(n-|B|)
最后的问题就是，2^n中n是个大数，不能直接套快速幂，怎么办？只需要将其转化为
ans = 2
for i = 0 to n.size()
ans = (quickPow(ans, 10) * quickPow(base, n[i] - '0')) % MOD
即可
另外好像更多人是用DP过的？有机会再补
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
const int N = 1e7 + 15;
typedef long long ll;
const ll MOD = 1000000007;
const int HIGHEST = 12;
char s[N];
int b[HIGHEST + 5];
bool used[5000];
int build(vector<int>& a, int n){
memset(b, 0, sizeof(b));
for(int i = 0; i < n; i++){
for(int j = HIGHEST; j >= 0; j--){
if((a[i] >> j & 1) == 0) continue;
if(b[j]) a[i] ^= b[j];
else{
b[j] = a[i];
for(int k = j - 1; k >= 0; k--) if(b[k] && (b[j] >> k & 1)) b[j] ^= b[k];
for(int k = j + 1; k <= HIGHEST; k++) if(b[k] >> j & 1) b[k] ^= b[j];
break;
}
}
}
int ret = 0;
for(int j = 0; j <= HIGHEST; j++){
if(b[j]) ret++;
}
return ret;
}
ll quickPow(ll a, ll b, ll m){
ll ans = 1, base = a;
while(b){
if(b&1) ans = (ans % m * (base % m)) % m;
base = (base % m * (base % m)) % m;
b >>= 1;
}
return ans;
}
ll extgcd(ll a, ll b, ll& x, ll& y){
ll d = a;
if(!b){
x = 1, y = 0;
}else{
d = extgcd(b, a%b, y, x);
y -= (a/b) * x;
}
return d;
}
ll getInv(ll a, ll m){
ll x, y;
extgcd(a, m, x, y);
return (x % m + m) % m;
}
ll toNum(){
ll ret = 0;
for(int i = 0; s[i]; i++){
ret = ret * 10 + s[i] - '0';
}
return ret;
}
int main(){
ll a, b, c, d, e, k, x1;
vector<int> vec;
while(~scanf("%s%lld", s, &x1)){
vec.clear();
memset(used, false, sizeof(used));
scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &e, &k);
vec.push_back(x1);
used[x1] = true;
while(true){
ll xpre = vec[vec.size() - 1];
ll res = ((a * xpre * xpre * xpre * xpre % k + b * xpre * xpre * xpre + c * xpre * xpre + d * xpre + e - 1) % k + k) % k + 1;
if(used[res]) break;
vec.push_back(res);
used[res] = true;
}
ll ans = 1;
for(int i = 0; s[i]; i++){
ans = (quickPow(ans, 10, MOD) * quickPow(2, s[i] - '0', MOD)) % MOD;
}
int cnt = strlen(s) <= 6 ? build(vec, min((ll)vec.size(), toNum())) : build(vec, vec.size());
ll tmp = ans;
tmp = (tmp * getInv(quickPow(2, cnt, MOD), MOD)) % MOD;
printf("%lld\n", (ans - tmp + MOD) % MOD);
}
}
