【AtCoder】ARC061

9953 단어

ARC061


C - 숫자/Many Formulas


이것은 사실\(10^5\)도 할 수 있습니다.
바로\(dp[i]\)는 i위까지의 방안 수를 표시하고\(sum[i]\)는 i위까지의 모든 방안의 숫자의 합을 표시하며\(pre[i]\)는 i위까지 확장이 끝난 숫자의 답을 기록합니다.
전송은\(dp[i] = dp[i - 1] * 2\)
\(sum[i] = sum[i - 1] * 10 + dp[i - 1] * (s[i] - '0')\)
\(pre[i] = pre[i - 1] * 2 + sum[i ]\)
#include 
#define fi first
#define se second
#define pii pair
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
') #define eps 1e-10 #define MAXN 100005 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template void read(T &res) { res = 0;T f = 1;char c = getchar(); 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) {x = -x;putchar('-');} if(x >= 10) { out(x / 10); } putchar('0' + x % 10); } char s[15]; int64 dp[15],sum[15],ans,pre[15]; int N; void Solve() { scanf("%s",s + 1); dp[0] = 1; N = strlen(s + 1); for(int i = 1 ; i <= N ; ++i) { sum[i] = sum[i - 1] * 10 + (s[i] - '0') * dp[i - 1]; dp[i] = dp[i - 1] * 2; if(i != N) pre[i] = pre[i - 1] * 2 + sum[i]; else pre[N] = pre[i - 1] + sum[i]; } out(pre[N]);enter; } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif Solve(); return 0; }

D - Snuke's Coloring


하나의\(3\times 3\)는 중심 칸 8개 방위에 자신을 더한 것으로 생각하고 각\(3\times 3\)가 중심 칸에 통계를 낸다.
모두\(H-2)(W-2)\)종이 발견되었으며, 0이 아닌 중심 칸은 검은 칸 부근 8개 방위에 검은 칸 자신만 추가할 수 있으며, 폭력 통계는
#include 
#define fi first
#define se second
#define pii pair
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
') #define eps 1e-10 #define MAXN 100005 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template void read(T &res) { res = 0;T f = 1;char c = getchar(); 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) {x = -x;putchar('-');} if(x >= 10) { out(x / 10); } putchar('0' + x % 10); } int H,W,N; int a[MAXN],b[MAXN]; int64 ans[MAXN]; map zz; map cnt; int dx[9] = {-1,1,0,0,0,1,1,-1,-1}; int dy[9] = {0,0,-1,1,0,1,-1,1,-1}; void Solve() { read(H);read(W);read(N); for(int i = 1 ; i <= N ; ++i) { read(a[i]);read(b[i]); zz[mp(a[i],b[i])] = 1; } for(int i = 1 ; i <= N ; ++i) { for(int k = 0 ; k < 9 ; ++k) { int tx = a[i] + dx[k]; int ty = b[i] + dy[k]; if(tx > 1 && tx < H && ty > 1 && ty < W) { int c = 0; for(int h = 0 ; h < 9 ; ++h) { if(zz[mp(tx + dx[h],ty + dy[h])]) ++c; } cnt[mp(tx,ty)] = c; } } } ans[0] = 1LL * (H - 2) * (W - 2); for(auto t : cnt) { ans[0]--; ans[t.se]++; } for(int i = 0 ; i <= 9 ; ++i) { out(ans[i]);enter; } } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif Solve(); return 0; }

E - 군의 지하철 여행 / Snuke's Subway Trip


변을 점으로 만들고 한 점에 연결된 변은 같은 색깔로 길이가 0인 변을 연결한다. 각 색깔 중에서 대표 변을 선택하고 새로 지은 점이 위로 연결되면 0이고 돌아오면 1이다. 1의 대가를 들여 이 점에서 다른 색깔의 변으로 옮기는 것을 의미한다.
디제이 뛰면 돼요.
#include 
#define fi first
#define se second
#define pii pair
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
') #define eps 1e-10 #define MAXN 400005 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template void read(T &res) { res = 0;T f = 1;char c = getchar(); 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) {x = -x;putchar('-');} if(x >= 10) { out(x / 10); } putchar('0' + x % 10); } struct node { int to,next,val; }E[MAXN * 10]; int head[MAXN],sumE; int N,M,Ncnt; int c[MAXN],dis[MAXN]; vector to[MAXN]; bool vis[MAXN]; priority_queue Q; void add(int u,int v,int c) { E[++sumE].to = v; E[sumE].next = head[u]; E[sumE].val = c; head[u] = sumE; } void Solve() { read(N);read(M); int q,p; Ncnt = M; for(int i = 1 ; i <= M ; ++i) { read(q);read(p);read(c[i]); to[q].pb(i);to[p].pb(i); } for(int i = 1 ; i <= N ; ++i) { sort(to[i].begin(),to[i].end(),[](int a,int b) {return c[a] < c[b];}); int nw = ++Ncnt; for(int j = 0 ; j < to[i].size() ; ++j) { int p = j; while(p < to[i].size() - 1 && c[to[i][p + 1]] == c[to[i][j]]) ++p; for(int h = j + 1 ; h <= p ; ++h) { add(to[i][j],to[i][h],0); add(to[i][h],to[i][j],0); } add(to[i][j],nw,0); add(nw,to[i][j],1); j = p; } } for(int i = 1 ; i <= Ncnt ; ++i) dis[i] = 1e9; for(auto t : to[1]) {dis[t] = 1;Q.push(mp(-1,t));} while(!Q.empty()) { pii now = Q.top();Q.pop(); if(vis[now.se]) continue; int u = now.se;vis[u] = 1; for(int i = head[u] ; i ; i = E[i].next) { int v = E[i].to; if(dis[v] > dis[u] + E[i].val) { dis[v] = dis[u] + E[i].val; Q.push(mp(-dis[v],v)); } } } int ans = 1e9; for(auto t : to[N]) ans = min(ans,dis[t]); if(ans >= 1e9) { puts("-1");return; } else {out(ans);enter;} } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif Solve(); return 0; }

F - 3인용 카드 카드


서로 다른 유저 서열은 서로 다른 패를 나누는 방식을 대표한다. 단지 같은 종류의 유저 서열에는 많은 패를 나누는 방식이 있을 수 있다. 이런 차이는 진 두 유저가 가지고 있는 패가 다른 가능성이 가져온 것이다.
그래서 우리는 A필승의 유저 서열은\(L>=N+1\)의 서열로 두 끝이 모두 a이고 중간에\(N-1\)개의 a와\(L-1-N)\)개\(b\) 또는\(c\)가 있으며 각각 자신의 상한선\(M\)과\(K\)을 초과하지 않는다는 것을 발견했다.
\(n\) 개\(b\) 또는\(c\) 가 있는 경우
그들의 합법적인 배열은 구간\([l,r]\)의\(\sum {i=l}^{r}\binom{i}{n}\)
i가 1로 커지면\([l,r]\) 두 단점의 변화는 1을 초과하지 않습니다
\(n\)의\([l,r]\)의 조합수를 이용하여\(n+1\)의\([l+1,r+1]\)의 조합수를 빠르게 산출할 수 있는 합을 발견하고 좌우단점의 비합법적인 상황을 수정하여 구간을 합법적으로 만들면 됩니다.
복잡도\(O (M + K)\
#include 
#define fi first
#define se second
#define pii pair
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
') #define eps 1e-10 #define MAXN 1000005 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template void read(T &res) { res = 0;T f = 1;char c = getchar(); 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) {x = -x;putchar('-');} if(x >= 10) { out(x / 10); } putchar('0' + x % 10); } const int MOD = 1000000007; int N,M,K,fac[MAXN],invfac[MAXN],pw[MAXN]; int s[MAXN]; int inc(int a,int b) { return a + b >= MOD ? a + b - MOD : a + b; } int mul(int a,int b) { return 1LL * a * b % MOD; } void update(int &x,int y) { x = inc(x,y); } int C(int n,int m) { if(n < m) return 0; else return mul(fac[n],mul(invfac[m],invfac[n - m])); } int fpow(int x,int c) { int res = 1,t = x; while(c) { if(c & 1) res = mul(res,t); t = mul(t,t); c >>= 1; } return res; } void Solve() { read(N);read(M);read(K); fac[0] = 1; for(int i = 1 ; i <= 1000000 ; ++i) fac[i] = mul(fac[i - 1],i); invfac[1000000] = fpow(fac[1000000],MOD - 2); for(int i = 999999 ; i >= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1); pw[0] = 1; for(int i = 1 ; i <= 1000000 ; ++i) pw[i] = mul(pw[i - 1],3); int l = 0,r = 0;s[0] = 1; for(int i = 1 ; i <= M + K ; ++i) { int tmp = inc(mul(s[i - 1],2),inc(C(i - 1,r + 1),MOD - C(i - 1,l))); ++r;++l; while(r + 1 <= i && r + 1 <= M) {update(tmp,C(i,r + 1));++r;} while(r > M) {update(tmp,MOD - C(i,r));--r;} while(i - l > K) {update(tmp,MOD - C(i,l));++l;} while(i - (l - 1) <= K && (l - 1) >= 0) {update(tmp,C(i,l - 1));--l;} s[i] = tmp; } int ans = 0; for(int i = 0 ; i <= M + K ; ++i) { int t = mul(C(N - 1 + i,N - 1),s[i]); t = mul(t,pw[M + K - i]); update(ans,t); } out(ans);enter; } int main() { #ifdef ivorysi freopen("f1.in","r",stdin); #endif Solve(); return 0; }

전재 대상:https://www.cnblogs.com/ivorysi/p/10893873.html

좋은 웹페이지 즐겨찾기