각종 OJ 문제 풀이 기록 6.9 - 6.15
94259 단어 bzoj
[템 플 릿] 다항식 구역
여러 가지 식 으로 역 원 을 구 하 는 오 의 를 배 웠 는데...
고려: B (x) C (x) = 1 (modxn)
항목 이동 및 제곱: B2 (x) C2 (x) − 2B (x) C (x) + 1 = 1 (modx2n)
이 항 획득: B (x) (2C (x) − B (x) C (x)) = 1 (modx2n)
그리고 modx 에서 배로 증가 할 수 있 습 니 다. 복잡 도 O (nlgn)
#include 꼬마 와 이 진 트 리
프로젝트 수의 생 성 함 수 는 G (z) 이 고 집합 C 의 생 성 함 수 는 C (z) 입 니 다.이 진 트 리 의 형 태 를 고려 하 다.그 는 점 이 하나 밖 에 없 거나 점 하나 와 두 개의 키 로 구성 되 어 있다.즉:
G(z)=G2(z)C(z)+1
해 득: G (z) = 1 ± 1 − 4C (z) √ C (z)
플러스 와 마이너스 번 호 를 고려 하 다.제목 에 c [i] ≥ 1 이 있 기 때문에 오른쪽 에 있 는 분모 상수 항 은 0 이 고 분자 상수 항 만 0 해 가 되 어야 정확 하 다.그래서 부 호 를 취해 야 한다.
분자 유리화
G(z)=21+1−4C(z)−−−−−−−−√
#include
", 2ll*e[i]%mod);
return 0;
}bzoj 4517: [Sdoi 2016] 배열 계수
선형 전달 역 원 을 학습 하 다.http://blog.miskcoo.com/2014/09/linear-find-all-invert
#include
", query(n, m));
}
return 0;
}bzoj 4403: 서열 통계
L, R 가입 을 고려 한 후 원래 수열 의 차이 점 수 는 10216 ° a0, a2,..., an * 10217 ° 이 고 반드시 만족 할 것 입 니 다.
∑kak=R−L=t
칸막이 법 으로 길이 가 n 인 방안 수 를 분석 하면 다음 과 같다.
(n+tt)
총 프로젝트 수:
∑1≤i≤n(i+tt)=∑1≤i−t≤n(i−t+tt)=∑t
(∗)=(n+t+1t+1)−(t+1t+1)=(n+t+1t+1)−1
그 다음 에 선형 전달 으로 역 원 을 추구 하고 luca 정리 로 조합 수 를 구하 면 된다.luca 공식 은:
(nm)=(n/pm/p)(n mod pm mod p)
#include
", (lucas(N+(R-L)+1, N, mod)-1+mod)%mod);
}
return 0;
}피 카 츄 구출
신 제 는... 전혀 못 해 요.http://hzwer.com/4639.html
#include
", i, f, c, j);
++top, edge[top] = (node){j, head[i], f, c, top+1}, head[i] = top;
++top, edge[top] = (node){i, head[j], 0, -c, top-1}, head[j] = top;
}
const int S = MAXN-2, T = MAXN-3, SS = MAXN-4, ST = MAXN-5;
const int inf = 1e9;
int n, m, k;
void push_lim(int i, int j, int f)
{
push(SS, j, f, 0), push(i, ST, f, 0);
push(i, j, inf, 0);
}
#define IN 0
#define OUT 1
int dis[MAXN], vis[MAXN], pre[MAXN], pre_edge[MAXN];
queue<int> que;
bool spfa(int &flow, int &cost)
{
for (int i = 0; i < MAXN; i++) dis[i] = inf;
// cout << dis[1] << endl;
memset(vis, 0, sizeof vis);
dis[SS] = 0, vis[SS] = 1, que.push(SS);
while (!que.empty()) {
int nd = que.front(); que.pop();
// cout << nd << endl;
//system("sleep 0.5");
vis[nd] = 0;
for (int i = head[nd]; i; i = edge[i].next) {
int to = edge[i].to, f = edge[i].flow, c = edge[i].cost;
if (!f || dis[to] <= dis[nd]+c) continue;
dis[to] = dis[nd]+c, pre[to] = nd, pre_edge[to] = i;
if (!vis[to])
vis[to] = 1, que.push(to);
}
}
if (dis[ST] >= inf) return 0;
int maxf = INT_MAX;
for (int i = ST; i != SS; i = pre[i]) maxf = min(maxf, edge[pre_edge[i]].flow);
for (int i = ST; i != SS; i = pre[i]) {
edge[pre_edge[i]].flow -= maxf;
edge[edge[pre_edge[i]].neg].flow += maxf;
}
flow += maxf, cost += maxf*dis[ST];
return 1;
}
void mcf(int &flow, int &cost)
{
push(T, S, inf, 0);
flow = cost = 0;
while (spfa(flow, cost));
}
inline int number(int nd, int id)
{
if (nd == 0) return n+n+1;
return nd+id*n;
}
int pw[MAXN], dd[MAXN], tp = 0;
int g[155][155];
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
g[i][j] = inf;
for (int i = 0; i <= n; i++) g[i][i] = 0;
for (int i = 1; i <= m; i++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
g[u][v] = g[v][u] = min(g[u][v], d);
}
for (int k = 0; k <= n; k++)
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++) {
if (k <= i && k <= j)
g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
}
for (int i = 0; i <= n; i++)
for (int j = i+1; j <= n; j++)
if (g[i][j] < inf)
push(number(i, OUT), number(j, IN), inf, g[i][j]);
push(S, number(0, IN), k, 0);
for (int i = 1; i <= n; i++) {
push_lim(number(i, IN), number(i, OUT), 1);
push(number(i, OUT), T, inf, 0);
}
push(number(n, OUT), T, k, 0);
int f = 0, cost = 0;
// puts("---");
mcf(f, cost);
cout << cost << endl;
return 0;
}bzoj 1212: [HNOI 2004] L 언어
hash 물이 지 나 갔 습 니 다.
#include
", k-1, j);
dp[j] |= dp[k-1];
}
}
}
int flag = 0;
for (int j = len; j >= 1; j--) {
if (dp[j]) {
printf("%d
", j);
flag = 1;
break;
}
}
if (!flag) puts("0");
}
return 0;
}AC 자동 해법:
#include
", i);
break;
}
}
if (!flag) printf("0
");
}
return 0;
}화합물
그냥 폭력 이면 넘 어 가 는 거 야??무슨 귀신
#include
", ans[i]);
return 0;
}bzoj 3173: [Tjoi 2013] 최 장 상승 서브 시퀀스
직접 밸 런 스 트 리 를 유지 하면 됩 니 다.하지만 splay 미 친 TLE, treap 가 벼 운 AC...
splay(TLE):
#include
", max_val[root]);
}
return 0;
}소모 전
허수 수 를 복습 하 다.
#include
", i, d, j);
if (!head_it[i]) it_kill_list[++list_top] = i;
edge_it[++top_it] = (node) {j, head_it[i], d}, head_it[i] = top_it;
}
int depth[MAXN];
long long len[MAXN];
int fa[MAXN][21], dfn[MAXN], dfn_top = 0;
int out[MAXN], n, m;
void dfs(int nd, int f)
{
fa[nd][0] = f, dfn[nd] = ++dfn_top;
// cerr << nd << " " << dfn_top << endl;
for (int i = head[nd]; i; i = edge[i].next) {
int to = edge[i].to;
if (to == f) continue;
depth[to] = depth[nd]+1, len[to] = min(len[nd], (long long)edge[i].dis);
dfs(to, nd);
}
out[nd] = dfn_top;
}
void init_lca()
{
for (int j = 1; j <= 20; j++)
for (int i = 1; i <= n; i++)
fa[i][j] = fa[fa[i][j-1]][j-1];
}
int lca(int a, int b)
{
if (depth[a] < depth[b]) swap(a, b);
for (int d = depth[a]-depth[b], i = 0; i <= 20; i++)
if ((d>>i)&1)
a = fa[a][i];
if (a == b) return a;
for (int i = 20; i >= 0; i--)
if (fa[a][i] != fa[b][i])
a = fa[a][i], b = fa[b][i];
return fa[a][0];
}
bool cmp(int a, int b)
{ return dfn[a] < dfn[b]; }
int stk[MAXN], stk_top = 0;
int in_stk[MAXN];
int mark[MAXN];
inline bool in_subtree(int nd, int T)
{ return dfn[nd] >= dfn[T] && dfn[nd] <= out[T];}
void build_tree(vector<int> &pt)
{
sort(pt.begin(), pt.end(), cmp);
// puts("Building tree");
// for (int i = 0; i < pt.size(); i++)
// cerr << dfn[pt[i]] << " ";
// cerr << endl;
for (int i = 0; i < pt.size(); i++)
mark[pt[i]] = 1;
mark[1] = 0;
for (int i = 0; i < pt.size(); i++) {
// cerr << pt[i] << endl;
if (!stk_top) stk[++stk_top] = pt[i], in_stk[pt[i]] = 1;
else {
while (stk_top > 1 && !in_subtree(pt[i], stk[stk_top-1]) &&
!in_subtree(pt[i], stk[stk_top])) {
in_stk[stk[stk_top]] = 0;
push_it(stk[stk_top-1], stk[stk_top], len[stk[stk_top]]);
stk_top--;
// cerr << stk_top << endl;
}
if (in_subtree(pt[i], stk[stk_top])) stk[++stk_top] = pt[i], in_stk[pt[i]] = 1;
else {
int bro = stk[stk_top--], t = lca(bro, pt[i]);
if (!stk_top || t != stk[stk_top]) stk[++stk_top] = t, in_stk[t] = 1;
push_it(stk[stk_top], bro, len[bro]), stk[++stk_top] = pt[i], in_stk[pt[i]] = 1;
}
}
}
while (stk_top > 1) {
// cerr << stk_top << endl;
push_it(stk[stk_top-1], stk[stk_top], len[stk[stk_top]]);
stk_top--;
}
stk_top = 0;
}
long long dfs_dp(int nd, int f)
{
if (mark[nd]) return inf;
long long ans = 0;
for (int i = head_it[nd]; i; i = edge_it[i].next) {
int to = edge_it[i].to, d = edge_it[i].dis;
// cerr << nd << "-->" << d <" << to << endl;
if (to == f) continue;
ans += min((long long)d, dfs_dp(to, nd));
if (ans > inf) ans = inf;
}
return ans;
}
void kill_tree(vector<int> &vec)
{
int num = vec.size();
for (int i = 1; i <= list_top; i++)
head_it[it_kill_list[i]] = 0;
list_top = 0;
top_it = 0;
for (int i = 0; i < num; i++)
mark[vec[i]] = 0;
}
vector<int> vec;
int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
push(u, v, d), push(v, u, d);
}
scanf("%d", &m);
for (int i = 1; i <= n; i++) len[i] = inf;
dfs(1, 0), init_lca();
for (int i = 1; i <= m; i++) {
int t, u; scanf("%d", &t);
vec.clear();
vec.push_back(1);
while (t--) {
scanf("%d", &u);
vec.push_back(u);
}
build_tree(vec);
printf("%lld
", dfs_dp(1, 0));
kill_tree(vec);
}
return 0;
}bzoj 1875: [SDOI 2009] HH 산책 가요.
데이터 범 위 는 우리 에 게 행렬 곱셈 이 라 고 알려 준다.
근 데 왜 돌아 오지 않 는 걸 제한해?
하나의 실행 가능 한 방안 은 변 점 을 교환 한 후에 점 에서 t 번 을 옮 기 면 변 에서 t - 1 번 을 옮 기 고 행렬 을 할 수 있다 는 것 이다.
#include
", ans);
return 0;
}토끼 와 벚꽃
나무 한 그루 를 정 하 다.한 점 을 삭제 하면 이 노드 의 가중치 와 아 이 를 아버지 에 게 걸 고 최대 몇 점 을 삭제 해 야 합 니까?
다음 과 같은 욕심 전략 을 고려 해 키 트 리 를 재 귀적 으로 만 들 고 최대한 많은 아들 을 욕심 내 서 삭제 합 니 다.
이 욕심 은 옳 은 것 이다. 위 에서 노드 를 삭제 하기 위해 아래 의 것 을 삭제 하 는 것 을 포기 할 수 없 기 때문이다.높 은 곳 일수 록 삭제 가 어렵 기 때문에...
#include
", cnt);
return 0;
}[SDOI 2015] 보물 찾기 게임
나무 사슬 과...
luogu 데이터 가 너무 약 하 잖 아.. 경계 가 안 걸 려..
오리 새끼
#include
", ans);
}
return 0;
}bzoj 3171 [Tjoi 2013] 순환 격
좋아 하 는 네트워크 스 트림 모델!
무 원 환 실행 가능 흐름 에서 하나의 회 로 는 확장 궤도 이다.이 문제 에 있어 그림 을 교차 하지 않 는 고리 로 만들어 야 한다. 각 노드 의 철거 점 과 유량 을 1 로 제한 하고 방향 을 바 꾸 는 데 비용 이 필요 하 며 원천 송금 이 없 는 최소 비용 으로 흐 르 면 된다.
#include
", i, f, c, j);
++top, edge[top] = (node){j, head[i], f, c, top+1}, head[i] = top;
++top, edge[top] = (node){i, head[j], 0, -c, top-1}, head[j] = top;
}
const int S = MAXN*MAXN*2-4, T = S+1;
inline void push_lim(int i, int j, int flim)
{
push(S, j, flim, 0), push(i, T, flim, 0);
}
int dis[MAXN*MAXN*2], vis[MAXN*MAXN*2];
queue<int> que;
int pre[MAXN*MAXN*2], pre_edge[MAXN*MAXN*2];
const int inf = 23333333;
bool spfa(int &flow, int &cost)
{
memset(dis, 127/3, sizeof dis);
memset(vis, 0, sizeof vis);
vis[S] = 1, dis[S] = 0, que.push(S);
while (!que.empty()) {
int nd = que.front(); que.pop(), vis[nd] = 0;
for (int i = head[nd]; i; i = edge[i].next) {
int to = edge[i].to, f = edge[i].flow, c = edge[i].cost;
if (!f || dis[to] <= dis[nd]+c) continue;
dis[to] = dis[nd]+c, pre[to] = nd, pre_edge[to] = i;
if (!vis[to])
vis[to] = 1, que.push(to);
}
}
if (dis[T] >= inf) return 0;
int maxf = inf;
for (int i = T; i != S; i = pre[i]) maxf = min(maxf, edge[pre_edge[i]].flow);
// cerr << maxf << " " << dis[T] << endl;
for (int i = T; i != S; i = pre[i]) {
edge[pre_edge[i]].flow -= maxf;
edge[edge[pre_edge[i]].neg].flow += maxf;
// cerr << "Arg : " << pre[i] << "-->"<< i << " Dis = "<< edge[pre_edge[i]].cost << endl;
}
flow += maxf, cost += dis[T]*maxf;
return 1;
}
void mcf(int &flow, int &cost)
{
flow = cost = 0;
while (spfa(flow, cost));
}
inline int number(int i, int j, int id)
{ return (i-1)*m+j+id*(n*m); }
#define IN 0
#define OUT 1
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", str+1);
for (int j = 1; j <= m; j++) {
switch(str[j]) {
case 'U' : g[i][j] = UP; break;
case 'L' : g[i][j] = LEFT; break;
case 'R' : g[i][j] = RIGHT; break;
case 'D' : g[i][j] = DOWN; break;
}
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
push_lim(number(i, j, IN), number(i, j, OUT), 1);
if (g[i][j] == UP) {
push(number(i, j, OUT), number(i>1?i-1:n, j, IN), 1, 0);
push(number(i, j, OUT), number(i1:1, j, IN), 1, 1);
push(number(i, j, OUT), number(i, j>1?j-1:m, IN), 1, 1);
push(number(i, j, OUT), number(i, j<m?j+1:1, IN), 1, 1);
} else if (g[i][j] == DOWN) {
push(number(i, j, OUT), number(i>1?i-1:n, j, IN), 1, 1);
push(number(i, j, OUT), number(i1:1, j, IN), 1, 0);
push(number(i, j, OUT), number(i, j>1?j-1:m, IN), 1, 1);
push(number(i, j, OUT), number(i, j<m?j+1:1, IN), 1, 1);
} else if (g[i][j] == LEFT) {
push(number(i, j, OUT), number(i>1?i-1:n, j, IN), 1, 1);
push(number(i, j, OUT), number(i1:1, j, IN), 1, 1);
push(number(i, j, OUT), number(i, j>1?j-1:m, IN), 1, 0);
push(number(i, j, OUT), number(i, j<m?j+1:1, IN), 1, 1);
} else if (g[i][j] == RIGHT) {
push(number(i, j, OUT), number(i>1?i-1:n, j, IN), 1, 1);
push(number(i, j, OUT), number(i1:1, j, IN), 1, 1);
push(number(i, j, OUT), number(i, j>1?j-1:m, IN), 1, 1);
push(number(i, j, OUT), number(i, j<m?j+1:1, IN), 1, 0);
}
}
int flow, cost;
mcf(flow, cost);
cout << cost << endl;
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj1010 장난감 포장 [결정 단조성 최적화 dp]하나의 모범 문제라고 할 수 있다.우리는 먼저 소박한 dp방정식을 얻을 수 있다. f[i]=min(f[j]+w(j,i)),j∈[0,i). w(j,i)는 j+1~i를 포장하여 운송하는 비용의 시간 복잡도는 O(n2)라...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
