【AtCoder】ARC061
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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.