天空彩票网站怎么做,做 了一个 家教 网站,加盟平台网站怎么做,工业企业网络推广方案1.设计图案 给你一个n*m的矩阵#xff0c;每个格子必须填或者不能填#xff0c;要用环和1*2的小方块填满它#xff0c;求方案数。 比如3*2#xff0c;每个格子都必须填 有6种填法。 n*m300 当时一看就觉得不可做然后就放弃了..... 题解#xff1a;有个结论#xff…1.设计图案 给你一个n*m的矩阵每个格子必须填或者不能填要用环和1*2的小方块填满它求方案数。 比如3*2每个格子都必须填 有6种填法。 n*m300 当时一看就觉得不可做然后就放弃了..... 题解有个结论 状压dp详细就是 按照从上到下从左到右dp用f[i][j][k]表示到第i行j列的格子轮廓线之上的格子的状态是k的方案数量。 如果这个格子不能填那么他上面的格子必须被填满上面格子也被填了的时候f[i][j][k]f[i][j-1][k](j!1)或者f[i-1][m][k](j1) 如果这个格子可以填那么先看一下它上面那个格子是否填满了没填满就一定要填填满了就不能竖着填了。然后看一下能不能横着填就可以了。 设x2^(j-1) f[i][j][k^x]f[i][j-1][k](j!1) 或者f[i-1][m][k](j1) 这句话表示的是填竖着的。 当j!1时判断一下是否可以横着填,可以的时候f[i][j][k|(x1)]f[i][j-1][k] 复杂度 nm * 2^(min(n,m)) 实际实现可以滚动数组这样简单很多。 代码 #includeiostream
#includecstdio
#define ll long long
#includecstring
using namespace std;
inline int read()
{int x0,f1;char chgetchar();while(ch0||ch9){if(ch-) f-1;chgetchar();}while(ch0ch9){xx*10ch-0; chgetchar();}return x*f;
}
int n,m,mod;
ll f[2][117];
bool b[305][305];
bool b2[305][305];int main()
{freopen(design.in,r,stdin);freopen(design.out,w,stdout);nread();mread();modread();for(int i1;in;i)for(int j1;jm;j)b[i][j](bool)read();if(nm){for(int i1;in;i)for(int j1;jm;j)b2[i][j]b[i][j];swap(n,m);for(int i1;in;i)for(int j1;jm;j)b[i][j]b2[j][i];}int nown1,pre0,to(1m)-1;f[pre][to]1;for(int i1;in;i){for(int j1;jm;j){for(int k0;kto;k){int x1j-1;if(!b[i][j]){if((k|x)k) f[nown][k](f[nown][k]f[pre][k])%mod; } else{f[nown][k^x](f[nown][k^x]f[pre][k])%mod; if(j!1(k|x)k((k|(x1))!k)b[i][j-1])f[nown][k|(x1)](f[nown][k|(x1)]f[pre][k])%mod;} }pre1-pre;nown1-nown;memset(f[nown],0,sizeof(f[nown])); } }ll ans(f[pre][to]*f[pre][to])%mod; printf(%lld\n,ans);return 0;
} 2.最优发射 大意有一个环有n个武器每个武器可以打死一个区间内的人。 多组数据每次给你很多人问至少要多少个武器可以全部打死..... n100000 人的总数200000 题解做法 倍增加速贪心。 我的做法 先删掉没用的边这样的话就可以保证边的l和r都是递增的。由于数据组数比较多所以显然不能每次遍历全部边。每个点直接二分一个能盖住它的边中最右能到哪里。 不考虑环显然是一个dp可以优化到nlogn 但是加上环之后就比较麻烦可以用一个lct维护一下dp路径 从1到m遍历从每一个点向它能转移的点连边如果它能越过环就向m1连边这样的话一个点的深度就是它一直到现在的点的dp值。 每个点如果有能跨过环的边那么就用能跨到的地方右边的第一个点的深度1更新一下答案。 复杂度nlogn 现场的时候写挂了只有60. #includeiostream
#includecstdio
#includealgorithm
#includecstring
#define INF 2000000000
#define ms(x) memset(x,0,sizeof(x))
using namespace std;
inline int read()
{int x0,f1;char chgetchar();while(ch0||ch9){if(ch-) f-1;chgetchar();}while(ch0ch9){xx*10ch-0; chgetchar();}return x*f;
}
int n,m,L,qq,ans;
int t[400005];
int c[200005][2];
int fa[200005],size[200005];
int rev[200005];
int qu[200005],top0;
int tf[200005];
bool yes;struct line{int l,r;
}ll[400005];bool cmp(line x,line y)
{return (x.ly.l)||(x.ly.lx.ry.r);
}inline bool isroot(int x){return c[fa[x]][0]!xc[fa[x]][1]!x;}
inline void update(int x){size[x]size[c[x][0]]size[c[x][1]]1;}void rotate(int x)
{//printf(rotate%d\n,x);int yfa[x],zfa[y],l,r;l(c[y][1]x),rl^1;if(!isroot(y)) c[z][c[z][1]y]x;fa[x]z;fa[y]x;fa[c[x][r]]y;c[y][l]c[x][r];c[x][r]y;update(y);update(x);
}void splay(int x)
{while(!isroot(x)){int yfa[x],zfa[y];if(!isroot(y)){if(c[z][1]y^c[y][1]x)rotate(x);else rotate(y);}rotate(x);}
}void access(int x)
{splay(x);while(fa[x]){int yfa[x];splay(y);c[y][1]x;update(y);splay(x);}
}
void link(int x,int y)
{access(x);splay(x);//rever(c[x][0]);access(y);splay(y);c[y][1]x;fa[x]y;
}void cut(int x)
{access(x);splay(x);fa[c[x][0]]0;c[x][0]0;
}int get(int x)
{int l1,rn,mid,ans-1;while(lr){mid(lr)1;if(ll[mid].lx) rmid-1;else{ ansll[mid].r;lmid1; } }return ans;
}int get2(int x)
{int l1,rm,mid,ans0;while(lr){mid(lr)1;if(t[mid]x) {ansmid;lmid1;}else {rmid-1;}}return ans;
}int check(int x)
{access(x);//splay(x);return size[c[x][0]];
}int main()
{freopen(launch.in,r,stdin);freopen(launch.out,w,stdout);nread();qqread();Lread();for(int i1;in;i){ll[i].lread();ll[i].rread();if(ll[i].rll[i].l) ll[i].rL;}for(int i1;in;i) if(ll[i].rL) {ll[n].l0;ll[n].rll[i].r-L; }sort(ll1,lln1,cmp);int j1;for(int i2;in;i){if(ll[i].rll[j].r) {ll[j]ll[i];} } nj;
// for(int i1;in;i) printf(%d %d %d\n,i,ll[i].l,ll[i].r);while(qq--){ms(fa);ms(c);ms(size);ms(rev);t[0]-1;yestrue;mread();for(int i1;im;i) t[i]read();sort(t1,tm1);ansINF;size[m1]1;int j1;for(int i2;im;i)if(t[i]!t[j]) t[j]t[i];mj;for(int i0;im;i) size[i]1;if(yes) for(int i1;im;i){int xget(t[i]);if(x-1||xt[i]) {puts(-1);yesfalse;break;}if(x-Lt[1]){ ansmin(ans,check(get2(x-L)1)1);link(i,m1);}else link(i,get2(x)1);}ansmin(ans,check(1));if(yes) printf(%d\n,ans);}return 0;
} 3.传输网络 有m条信息n个传输装置。 每个装置可以把一个范围a-b内的全部信息转移到cacb但是需要d点费用 现在要把全部信息都转移到一个点求最小费用。 m10^9 n10^5 先离散一下再用两个线段树维护第一条和最后一条信息到每个点c的距离。 然后按dp做就行了。 现场只写了n^3 dp 只有50分...... #includeiostream
#includecstdio
#includealgorithm
#define ll long long
#define N 262144
#define INF 1000000000000000000LL
using namespace std;
inline ll llread()
{ll x0,f1;char chgetchar();while(ch0||ch9){if(ch-) f-1;chgetchar();}while(ch0ch9){xx*10ch-0; chgetchar();}return x*f;
}
inline int read()
{int x0,f1;char chgetchar();while(ch0||ch9){if(ch-) f-1;chgetchar();}while(ch0ch9){xx*10ch-0; chgetchar();}return x*f;
}
int n,m,cnt0;
ll ansINF;
int s[300005];
struct ma{int l,r,c;ll d;
}a[100005];ll T1[600005],T2[600005];ll query(ll*T,int l,int r)
{ll minnINF;for(lN-1,rN1;l^r^1;l1,r1){if(~l1) minnmin(minn,T[l1]);if( r1) minnmin(minn,T[r-1]); }return minn;
}void renew(ll*T,int x,ll ad)
{T[xN]min(T[x],ad);for(x1;x;x1)T[x]min(T[x1],T[(x1)1]);
} void init()
{for(int i1;iN*2;i)T1[i]T2[i]INF;
}int main()
{freopen(network.in,r,stdin);freopen(network.out,w,stdout);nread();mread();for(int i1;in;i){a[i].lread();a[i].rread();a[i].cs[i]read();a[i].dllread();}s[n1]1;s[n2]m;sort(s1,sn3);init();int j0;for(int i1;in2;i){if(s[i]!s[i-1])s[j]s[i];}cntj;renew(T1,1,0);renew(T2,cnt,0);for(int i1;in;i){a[i].llower_bound(s1,scnt1,a[i].l)-s;a[i].rupper_bound(s1,scnt1,a[i].r)-s-1;a[i].clower_bound(s1,scnt1,a[i].c)-s;}for(int i1;in;i){if(a[i].la[i].r||a[i].lcnt||a[i].rcnt) continue;ll x1query(T1,a[i].l,a[i].r);ll x2query(T2,a[i].l,a[i].r);ansmin(ans,x1x2a[i].d);renew(T1,a[i].c,x1a[i].d);renew(T2,a[i].c,x2a[i].d); }if(ansINF) printf(%lld\n,ans);else puts(-1);return 0;
} 转载于:https://www.cnblogs.com/FallDream/p/liankao219.html
