今天挂的有点惨……
T1.forging
这道题自己在考试的时候想出来了……
这题是一个期望递推。我们首先考虑这么一件事，一枚硬币，你抛到正面停止，抛到反面继续抛，问期望抛的次数。是两次。我们假设期望抛x次，因为期望对于后面没有影响，所以有如下方程：
x = 0.5 × 0 + 0.5 × x + 1，x = 2.
那么我们就可以通过当前合成的概率知道合成的期望次数了。然后一次合成我们需要一把i级的武器，我们只需要1把i-2级的武器和期望次数把的i-1级的武器，所以我们就可以这样递推计算，然后结束。
结果一是因为自己智障的在两个0级刀合成的时候忘记取max，加上自己空间开的过大，100变0分可还行。
看下std……自己改完的代码好像丢了……
#include#include #include #include using namespace std;typedef long long ll;const int p=998244353;const int N=1e7+5;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}int inv[N],b[N],c[N],f[N];inline int sub(int x,int y){ x-=y;if(x<0)x+=p;return x;}int main(){ freopen("forging.in","r",stdin);freopen("forging.out","w",stdout); inv[1]=1; for(int i=2;i
T2.division
这道题当时做的时候没想出来什么……于是好像写了个暴力骗了20。
后来学姐说是CRT……？没大听懂，copy一下题解……
std：
#include#define enter putchar('\n')#define space putchar(' ')using namespace std;template void read(T &res){ res = 0; char c = getchar(); T f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); } res *= f;}template void out(T x){ if(x < 0) { putchar('-'); x = -x; } if(x >= 10) { out(x / 10); } putchar('0' + x % 10);}int id;int a[20005],tot,prime[20005];bool nonprime[20005];int mul(int a,int b,int MOD){ return 1LL * a * b % MOD;}int fpow(int x,int c,int MOD){ int res = 1,t = x; while(c) { if(c & 1) res = res * t % MOD; t = t * t % MOD; c >>= 1; } return res;}int Calc(int p,int m){ memset(nonprime,0,sizeof(nonprime)); tot = 0; a[1] = 1; a[p] = 0; for(int i = 2 ; i < p ; ++i) { if(!nonprime[i]) { a[i] = fpow(i,m,p); prime[++tot] = i; } for(int j = 1 ; j <= tot ; ++j) { if(i * prime[j] > 10000) break; a[i * prime[j]] = a[i] * a[prime[j]] % p; nonprime[i * prime[j]] = 1; if(i % prime[j] == 0) break; } } int res = 0; for(int i = 1 ; i <= p ; ++i) { int t = a[i] - i + p; if(t >= p) t -= p; res += (t == 0); } return res;}void Solve(){ int ans = 1; int c,m; read(c); read(m); int p = 0; for(int i = 1 ; i <= c ; ++i) { read(p); ans = mul(ans,Calc(p,m),998244353); } out(ans); enter;}int main(){ freopen("division.in","r",stdin); freopen("division.out","w",stdout); read(id); int T; read(T); while(T--) Solve();}
T3.money
这道题仍然是不会的状态……考试的时候骗到了10分。
正解是用倍增求出链上最小值，然后合并的时候启发式合并，用倍增记一下边的方向（？？？）
表示还是不懂……看一下std吧orz
#include#include #include #include #include #include #define space putchar(' ')#define enter putchar('\n')typedef long long ll;using namespace std;template void read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x;}template void write(T x){ if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10);}const int N = 100005, INF = 0x3f3f3f3f;int n, m, lastans;int ecnt, nxt[2*N], go[2*N], adj[N], edir[2*N], emi[2*N];int sze[N], bel[N], dep[N];int anc[N][20], mi[N][20], dir[N][20];void out(){ for(int i = 1; i <= n; i++) for(int j = 0; anc[i][j]; j++) printf("anc[%d][%d] = %d, dir = %d, mi = %d\n", i, j, anc[i][j], dir[i][j], mi[i][j]);}void adde(int u, int v, int d, int w){ go[++ecnt] = v; nxt[ecnt] = adj[u]; adj[u] = ecnt; edir[ecnt] = d; emi[ecnt] = w;}void dfs(int u, int pre, int rt){ bel[u] = rt; dep[u] = dep[pre] + 1; for(int i = 0; i < 19; i++){ anc[u][i + 1] = anc[anc[u][i]][i]; mi[u][i + 1] = min(mi[u][i], mi[anc[u][i]][i]); dir[u][i + 1] = dir[u][i] | dir[anc[u][i]][i]; } for(int e = adj[u], v; e; e = nxt[e]) if((v = go[e]) != pre){ anc[v][0] = u; mi[v][0] = emi[e]; dir[v][0] = edir[e] ^ 3; dfs(v, u, rt); }}void add(int u, int v, int w){ adde(u, v, 1, w); adde(v, u, 2, w); int d = sze[bel[u]] > sze[bel[v]] ? 2 : 1; if(d == 2) swap(u, v); anc[u][0] = v, mi[u][0] = w, dir[u][0] = d; sze[bel[v]] += sze[bel[u]]; dfs(u, v, bel[v]);}int query(int u, int v){ if(bel[u] != bel[v]) return 0; int d = 3, ret = INF; if(dep[u] > dep[v]) swap(u, v), d = 0; for(int i = 19; i >= 0; i--) if(dep[v] - (1 << i) >= dep[u]){ if(dir[v][i] != (1 ^ d)) return 0; ret = min(ret, mi[v][i]); v = anc[v][i]; } if(u == v) return ret; for(int i = 19; i >= 0; i--) if(anc[u][i] != anc[v][i]){ if(dir[v][i] != (1 ^ d) || dir[u][i] != (2 ^ d)) return 0; ret = min(ret, min(mi[v][i], mi[u][i])); u = anc[u][i]; v = anc[v][i]; } if(dir[v][0] != (1 ^ d) || dir[u][0] != (2 ^ d)) return 0; ret = min(ret, min(mi[v][0], mi[u][0])); return ret;}int main(){ freopen("money.in", "r", stdin); freopen("money.out", "w", stdout); read(n), read(m); for(int i = 1; i <= n; i++) bel[i] = i, sze[i] = 1; int op, a, b, c; while(m--){ read(op), read(a), read(b); a = (a + lastans) % n + 1; b = (b + lastans) % n + 1; if(op == 0) read(c), c = (c + lastans) % n + 1, add(a, b, c); else write(lastans = query(a, b)), enter; } return 0;}