博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Lesnoe Ozero 2017. BSUIR Open 2017
阅读量:5105 次
发布时间:2019-06-13

本文共 14514 字,大约阅读时间需要 48 分钟。

A. Tree Orientation

树形DP,$f[i][j][k]$表示$i$的子树中有$j$个汇点,$i$往父亲的树边方向为$k$的方案数。

转移则需要另一个DP:$g[i][j][k]$表示考虑前$i$个儿子,子树中有$j$个汇点,$i$的出边个数是否是$0$的方案数。

时间复杂度$O(n^2)$。

#include
const int N=1010,P=1000000007;int n,m,i,x,y,g[N],v[N<<1],nxt[N<<1],ed;int f[N][N][2];int size[N];int pre[N][2],now[N][2];inline void add(int x,int y){ v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}inline void up(int&a,int b){a=(a+b)%P;}void dfs(int x,int y){ for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x); size[x]=1; for(int i=0;i<=1;i++)for(int j=0;j<2;j++)pre[i][j]=0; pre[0][0]=1; for(int i=g[x];i;i=nxt[i]){ int u=v[i]; if(u==y)continue; for(int j=0;j<=size[x]+size[u];j++)for(int k=0;k<2;k++)now[j][k]=0; for(int j=0;j<=size[x];j++)for(int k=0;k<2;k++)if(pre[j][k]) for(int a=0;a<=size[u];a++)for(int b=0;b<2;b++)if(f[u][a][b]){ up(now[j+a][k||b],1LL*pre[j][k]*f[u][a][b]%P); } size[x]+=size[u]; for(int j=0;j<=size[x];j++)for(int k=0;k<2;k++)pre[j][k]=now[j][k]; } for(int j=0;j<=size[x];j++)for(int k=0;k<2;k++){ for(int o=0;o<2;o++){ if(x==1&&!o)continue; up(f[x][j+(!(k||!o))][o],pre[j][k]); } }}int main(){ scanf("%d%d",&n,&m); for(i=1;i

  

B. A Masterpiece

行列交换不影响答案,根据这一条构造即可。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }#define MS(x, y) memset(x, y, sizeof(x))#define ls o<<1#define rs o<<1|1typedef long long LL;typedef unsigned long long UL;typedef unsigned int UI;template
inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }template
inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;template
inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }int casenum, casei;int n;void solve(){ if(n == 1){ puts("1"); puts("1"); return; } if(n == 2 || n == 3){ puts("-1"); return; } printf("%d\n", n); for(int i = 1; i <= n; i ++){ for(int j = 2; j <= n; j += 2){ printf("%d ", (i - 1) * n + j); } for(int j = 1; j <= n; j += 2){ printf("%d ", (i - 1) * n + j); } puts(""); }}int main(){ scanf("%d", &n); solve(); return 0;}/*【trick&&吐槽】【题意】【分析】【时间复杂度&&优化】*/

  

C. Auction

从$n$开始倒推出哪些数字是必胜/必败态,每次数字集合都可以压缩成一个区间,且最多推$O(\log n)$步。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }#define MS(x, y) memset(x, y, sizeof(x))#define ls o<<1#define rs o<<1|1typedef long long LL;typedef unsigned long long UL;typedef unsigned int UI;template
inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }template
inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;template
inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }int casenum, casei;LL n;bool solve(){ LL l = n + 1; LL r; int tp = 1; while(1) { r = l - 1; if(tp == 1) { l = l / 9 + (l % 9 > 0); } else { l = l / 2 + (l % 2 > 0); } if(l <= 1 && r >= 1) { return tp; } tp = 1 ^ tp; }}int main(){ scanf("%d", &casenum); for (casei = 1; casei <= casenum; ++casei) { scanf("%lld", &n); puts(solve() ? "YES" : "NO"); } return 0;}/*【trick&&吐槽】【题意】【分析】【时间复杂度&&优化】*/

  

D. Deck Building

将过程倒过来,那么可以看作按$k$从大到小选取若干点,要求$s$是波浪形,且相邻两段$i\rightarrow j$的代价为$j$前面$s_i$到$s_j$之间的点数。

设$f[i][j]$表示考虑前$i$个点且第$i$个点必选,与上一个点的大小关系为$j$的方案数,$g[][]$表示代价之和,则转移可以用线段树打标记优化。

时间复杂度$O(n\log n)$。

#include
#include
using namespace std;typedef long long ll;const int N=100010,M=262150,P=1000000007;int n,m,i,j,k,x,b[N],f[N][2],g[N][2],ans,ma,mi;int bit[N];struct E{int s,k;}a[N];inline bool cmp(const E&a,const E&b){return a.k>b.k;}inline void modify(int x){for(;x<=n;x+=x&-x)bit[x]++;}inline int getpre(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}struct DS{int f[M],g[M],tag[M],v[M];inline void tag1(int x,int p){ tag[x]=(tag[x]+p)%P; v[x]=(v[x]+1LL*p*f[x])%P;}inline void pb(int x){ if(tag[x]){ tag1(x<<1,tag[x]); tag1(x<<1|1,tag[x]); tag[x]=0; }}inline void up(int x){ f[x]=(f[x<<1]+f[x<<1|1])%P; g[x]=(g[x<<1]+g[x<<1|1])%P; v[x]=(v[x<<1]+v[x<<1|1])%P;}void change(int x,int a,int b,int c,int d,int p){ if(c<=a&&b<=d){ tag1(x,p); return; } pb(x); int mid=(a+b)>>1; if(c<=mid)change(x<<1,a,mid,c,d,p); if(d>mid)change(x<<1|1,mid+1,b,c,d,p); up(x);}void addf(int x,int a,int b,int c,int p){ if(a==b){ f[x]=(f[x]+p)%P; v[x]=(v[x]+1LL*tag[x]*p)%P; return; } pb(x); int mid=(a+b)>>1; if(c<=mid)addf(x<<1,a,mid,c,p); else addf(x<<1|1,mid+1,b,c,p); up(x);}void addg(int x,int a,int b,int c,int p){ if(a==b){ g[x]=(g[x]+p)%P; v[x]=(v[x]+p)%P; return; } pb(x); int mid=(a+b)>>1; if(c<=mid)addg(x<<1,a,mid,c,p); else addg(x<<1|1,mid+1,b,c,p); up(x);}int askf(int x,int a,int b,int c,int d){ if(c<=a&&b<=d)return f[x]; pb(x); int mid=(a+b)>>1,t=0; if(c<=mid)t=askf(x<<1,a,mid,c,d); if(d>mid)t+=askf(x<<1|1,mid+1,b,c,d); return t%P;}int askv(int x,int a,int b,int c,int d){ if(c<=a&&b<=d)return v[x]; pb(x); int mid=(a+b)>>1,t=0; if(c<=mid)t=askv(x<<1,a,mid,c,d); if(d>mid)t+=askv(x<<1|1,mid+1,b,c,d); return t%P;}}g0,g1;int main(){ scanf("%d",&n);m=n+1; for(i=1;i<=n;i++)scanf("%d%d",&a[i].s,&a[i].k),b[i]=a[i].s; sort(a+1,a+n+1,cmp); sort(b+1,b+n+1); for(i=1;i<=n;i++)a[i].s=lower_bound(b+1,b+n+1,a[i].s)-b; ma=-N,mi=N; for(i=1;i<=n;i=j){ for(j=i;j<=n&&a[i].k==a[j].k;j++){ x=a[j].s; if(ma<=x)f[j][0]=1; if(mi>=x)f[j][1]=1; int cnt=g1.askf(1,0,m,x+1,m);//sum f (f[j][0]+=cnt)%=P; (g[j][0]+=g1.askv(1,0,m,x+1,m))%=P;//sum g+f*w g[j][0]=(g[j][0]-1LL*getpre(x)*cnt)%P; cnt=g0.askf(1,0,m,0,x-1);//sum f (f[j][1]+=cnt)%=P; (g[j][1]+=g0.askv(1,0,m,0,x-1))%=P;//sum g+f*w g[j][1]=(g[j][1]+1LL*getpre(x-1)*cnt)%P; } for(k=i;k

  

E. The secret of betting

$f[i][S]$表示考虑前$i$个人,$i$往前往后$k$个人的位置确定情况为$S$的方案数,只有恰好$k$个$1$的状态是有效的。

当$n$比较小时暴力转移,否则矩阵快速幂加速。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }#define MS(x, y) memset(x, y, sizeof(x))#define MC(x, y) memcpy(x, y, sizeof(x))#define ls o<<1#define rs o<<1|1typedef long long LL;typedef unsigned long long UL;typedef unsigned int UI;template
inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }template
inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;template
inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }int casenum, casei;LL n; int K;int ID;int bts[1 << 20];int stb[1 << 20];int f[2][(int)2e5 + 10];const int G = 72;struct MX{ int v[G][G]; void O() { MS(v, 0); } void E() { MS(v, 0); for(int i = 0; i < G; ++i)v[i][i] = 1; } MX operator * (const MX & b)const { MX c; c.O(); for(int i = 0; i < G; ++i) { for(int j = 0; j < G; ++j) { for(int k = 0; k < G; ++k) { c.v[i][j] = (c.v[i][j] + (LL)v[i][k] * b.v[k][j]) % Z; } } } return c; } MX operator ^ (LL p)const { MX y; y.E(); MX x; MC(x.v, v); while(p) { if(p & 1)y = y * x; x = x * x; p >>= 1; } return y; }}a, b;vector
vt[1 << 20];int main(){ while(~scanf("%lld%d", &n, &K)) { int top = 1 << (K * 2); ID = 0; for(int j = 0; j < top; ++j)if(__builtin_popcount(j) == K) { stb[ID] = j; bts[j] = ID++; } //printf("%d\n", ID); int sta = 0; for(int i = 0; i < K; ++i) { sta |= 1 << (K + i); } if(K <= 4) { int ww = bts[sta]; a.O(); a.v[0][ww] = 1; b.O(); for(int i = 0; i < ID; ++i) { int x = stb[i]; if(x & 1) { int w = bts[x / 2 | top / 2]; b.v[i][w] = 1; } else { for(int k = 1; k < K + K; ++k)if(x >> k & 1) { int w = bts[(x ^ 1 << k) / 2 | top / 2]; b.v[i][w] = 1; } int w = bts[x / 2]; b.v[i][w] = 1; } } a = a * (b ^ n); printf("%d\n", a.v[0][ww]); } else { for(int x = 0; x < top; ++x)if(__builtin_popcount(x) == K) { for(int j = 1; j < K + K; ++j)if(x >> j & 1) { int w = bts[(x ^ 1 << j) / 2 | top / 2]; vt[x].push_back(w); } } int ww = bts[sta]; MS(f, 0); f[0][ww] = 1; for(int v = 0; v < n; ++v) { int now = v & 1; int nxt = ~v & 1; //MS(f[nxt], 0); for(int i = 0; i < ID; ++i) { f[nxt][i] = 0; } for(int i = 0; i < ID; ++i)if(f[now][i]) { int x = stb[i]; if(x & 1) { int w = bts[x >> 1 | top >> 1]; gadd(f[nxt][w], f[now][i]); } else { for(auto w : vt[x]) { gadd(f[nxt][w], f[now][i]); } /* for(int k = 1; k < K + K; ++k)if(x >> k & 1) { int w = bts[(x ^ 1 << k) / 2 | top / 2]; gadd(f[nxt][w], f[now][i]); } */ int w = bts[x >> 1]; gadd(f[nxt][w], f[now][i]); } } } printf("%d\n", f[n & 1][ww]); } } return 0;}/*【trick&&吐槽】【题意】【分析】【时间复杂度&&优化】1000 510000 5100000 5*/

  

F. Financial Reports

设$f[i][j][x][y]$表示考虑前$i$个位置,目前选取区间的状态为$j$(即未选,正在选,已选),区间外选取了$x$个数,区间内丢弃了$y$个数时,区间和的最大值。

注意输出方案时要特判交换不导致答案变优的情况。

时间复杂度$O(n)$。

#include
#include
using namespace std;typedef long long ll;typedef pair
P;typedef pair
W;typedef pair
PI;const int N=100010;const ll inf=1LL<<60;int n,i,j,x,y;ll a[N];PI f[N][3][2][2],ans;//how many in and how many outinline void up(PI&t,ll a,int b,int c,int d,int e){ t=max(t,PI(a,W(P(b,c),P(d,e))));}int main(){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%lld",&a[i]); for(i=0;i<=n;i++)for(j=0;j<3;j++)for(x=0;x<2;x++)for(y=0;y<2;y++)f[i][j][x][y]=PI(-inf,W(P(0,0),P(0,0))); f[0][0][0][0]=PI(0,W(P(0,0),P(0,0))); for(i=1;i<=n;i++)for(x=0;x<2;x++)for(y=0;y<2;y++){ //consider i PI t=f[i-1][0][x][y]; int A=t.second.first.first; int B=t.second.first.second; int C=t.second.second.first; int D=t.second.second.second; if(t.first>-inf){ //still the stage up(f[i][0][x][y],t.first,A,B,C,D); //swap in if(!x)up(f[i][0][1][y],t.first+a[i],i,B,C,D); //new stage up(f[i][1][x][y],t.first+a[i],A,B,i,D); //swap out if(!y)up(f[i][1][x][1],t.first,A,i,i,D); } t=f[i-1][1][x][y]; A=t.second.first.first; B=t.second.first.second; C=t.second.second.first; D=t.second.second.second; if(t.first>-inf){ //still the stage up(f[i][1][x][y],t.first+a[i],A,B,C,i); //swap out if(!y)up(f[i][1][x][1],t.first,A,i,C,i); //new stage up(f[i][2][x][y],t.first,A,B,C,D); //swap in if(!x)up(f[i][2][1][y],t.first+a[i],i,B,C,D); } t=f[i-1][2][x][y]; A=t.second.first.first; B=t.second.first.second; C=t.second.second.first; D=t.second.second.second; if(t.first>-inf){ //still the stage up(f[i][2][x][y],t.first,A,B,C,D); //swap in if(!x)up(f[i][2][1][y],t.first+a[i],i,B,C,D); } } ans=max(f[n][1][1][1],f[n][2][1][1]); ans=max(ans,f[n][1][0][0]); ans=max(ans,f[n][2][0][0]); int A=ans.second.first.first; int B=ans.second.first.second; int C=ans.second.second.first; int D=ans.second.second.second; if(!A){ A=C,B=D; if(A==B){ if(B==1)B=2; else B=1; } } if(A>B)swap(A,B); printf("%lld\n%d %d",ans.first,A,B);}

  

G. Moore’s Law

从$n-1$的答案开始往最高位补$1$或者$2$,必然有解。

#include
#include
using namespace std;typedef long long ll;int n,i,len,f[1111111];ll m;bool check(){ ll t=0; for(int i=len;i;i--)t=(t*10+f[i])%m; return t==0;}int main(){ scanf("%d",&n); m=1LL<

  

H. Plagiarism

$f[i][j][x][y]$表示考虑$a$长度为$i$的前缀以及$b$长度为$j$的前缀,$a$和$b$正在匹配的部分长度分别为$x$和$y$时的最小串长。

时间复杂度$O(n^4)$。

#include
#include
#include
using namespace std;const int N=110,inf=10000000;int K,n,m,o,i,j,k,x,y,t,f[2][N][N][N],ans;char a[N],b[N];inline void up(int&x,int y){ x>y?(x=y):0;}int main(){ scanf("%d%s%s",&K,a+1,b+1); n=strlen(a+1); m=strlen(b+1); for(j=0;j<=m;j++)for(x=0;x<=n;x++)for(y=0;y<=m;y++)f[0][j][x][y]=inf; f[0][0][0][0]=0; for(i=o=0;i<=n;i++,o^=1){ for(j=0;j<=m;j++)for(x=0;x<=n;x++)for(y=0;y<=m;y++)f[o^1][j][x][y]=inf; for(j=0;j<=m;j++)for(x=n;~x;x--)for(y=m;~y;y--)if(f[o][j][x][y]
=K)up(f[o][j][0][y],t); if(y>=K)up(f[o][j][x][0],t); if(x>=K&&y>=K)up(f[o][j][0][0],t); t++; if(i

  

I. Number builder

将$1$和$2$交替放是最优的。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }#define MS(x, y) memset(x, y, sizeof(x))#define ls o<<1#define rs o<<1|1typedef long long LL;typedef unsigned long long UL;typedef unsigned int UI;template
inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }template
inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;template
inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }int casenum, casei;int n;char a[105], b[105];int main(){ while(~scanf("%d", &n)) { int p1 = 0; int m = n; int x = 1; while(m > 0) { a[p1++] = '0' + x; m -= x; if(m<0) { p1 = 0; break; } x = 3 - x; } a[p1] = 0; int p2 = 0; m = n; x = 2; while(m > 0) { b[p2++] = '0' + x; m -= x; if(m<0) { p2 = 0; break; } x = 3 - x; } b[p2] = 0; if(p1 != p2) { puts(p1 > p2 ? a : b);; } else { puts(strcmp(a, b) > 0 ? a : b); } } return 0;}/*【trick&&吐槽】【题意】【分析】【时间复杂度&&优化】*/

  

J. Find a triangle

首先二分出三角形的包围盒,然后确定哪个顶点是三角形的顶点,之后二分即可。

 

转载于:https://www.cnblogs.com/clrs97/p/7689847.html

你可能感兴趣的文章
Activiti入门 -- 环境搭建和核心API简介
查看>>
struts.convention.classes.reload配置为true,tomcat启动报错
查看>>
MySQL的并行复制多线程复制MTS(Multi-Threaded Slaves)
查看>>
好玩的-记最近玩的几个经典ipad ios游戏
查看>>
MySQL更改默认的数据文档存储目录
查看>>
PyQt5--EventSender
查看>>
Sql Server 中由数字转换为指定长度的字符串
查看>>
Java 多态 虚方法
查看>>
Unity之fragment shader中如何获得视口空间中的坐标
查看>>
万能的SQLHelper帮助类
查看>>
tmux的简单快捷键
查看>>
[Swift]LeetCode922.按奇偶排序数组 II | Sort Array By Parity II
查看>>
Html5 离线页面缓存
查看>>
《绿色·精简·性感·迷你版》易语言,小到不可想象
查看>>
Android打包key密码丢失找回
查看>>
VC6.0调试技巧(一)(转)
查看>>
类库与框架,强类型与弱类型的闲聊
查看>>
webView添加头视图
查看>>
php match_model的简单使用
查看>>
在NT中直接访问物理内存
查看>>