codeforces选做

时间：2022-09-03 19:45:40

收录了最近本人完成的一部分codeforces习题，不定期更新

所以其实是补题记录QAQ

codeforces 1132E Knapsack

注意到如果只使用某一种物品，那么这八种物品可以达到的最小相同重量为\(840\)

故答案一定可以被写成\(840k+x（k,x\in N_+)\)，我们将\(x\)称为”余下的部分”

故而设\(dp[i][j]\)为当前考虑了前\(i\)个物品，它们所占的余下的部分的重量为\(j\)时，最多可以组成多少个\(840\)

对于每个\(i\)预处理出枚举上界暴力转移即可

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

#define maxd 1000000007

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

ll w,a[10],ans=0,dp[9][100100];

ll read()

{

	ll x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

int main()

{

	w=read();

	rep(i,1,8) a[i]=read();

	ll maxp=8*840;

	memset(dp,-1,sizeof(dp));

	dp[0][0]=0;

	rep(i,1,8)

	{

		rep(j,0,maxp)//余下的重量

		{

			if (dp[i-1][j]==-1) continue;

			ll k=min(1ll*840/i,a[i]);

			rep(p,0,k)//当前有多少作为余下的部分

			{

				dp[i][j+p*i]=max(dp[i][j+p*i],dp[i-1][j]+(a[i]-p)/(840/i));

			}

		}

	}

	ll ans=0;

	rep(i,0,min(w,maxp))

	{

		if (dp[8][i]==-1) continue;

		ans=max(ans,i+min((w-i)/840,dp[8][i])*840);

	}

	printf("%lld",ans);

	return 0;

}

codeforces1154G Minimum Possible LCM

根据\(lcm(x,y)=\frac{xy}{gcd(x,y)}\)进行计算

枚举约数\(d\)，每次找到满足\(d|x\)的最小的两个\(x\)，用它们更新答案即可

为什么这样做可行？我们假设满足\(d|x\)的数从小到大一次为\(a_1,a_2,\cdots,a_k\)

不妨对\(a_1,a_2,a_k(k>2)\)这三个数进行分析，并且我们保证\(gcd(a_1,a_k)=d\)，否则我们可以在枚举更大的\(d\)的时候考虑到这一组

  • 若\(gcd(a_1,a_2)=d\)，那么一定有\(\frac{a_1a_2}{gcd(a_1,a_2)}<\frac{a_1a_k}{gcd(a_1,a_k)}\)
  • 若\(gcd(a_1,a_2)>d\)，则\(\frac{a_1a_2}{gcd(a_1,a_2)}<\frac{a_1a_2}{d}<\frac{a_1a_k}{d}\)

证毕

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

int n,a[1001000],cnt[10010000];

vector<int> ans;

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

ll gcd(ll x,ll y)

{

	if (!y) return x;else return gcd(y,x%y);

}

int main()

{

	n=read();ll maxd=0;

	rep(i,1,n) {a[i]=read();cnt[a[i]]++;maxd=max(maxd,1ll*a[i]);}

	ll lcm=(ll)1e18+7,val1,val2;

	rep(i,1,maxd)

	{

		int j;ans.clear();

		for (j=i;j<=maxd;j+=i)

		{

			if (!cnt[j]) continue;

			int tmp=cnt[j];

			while ((tmp) && (ans.size()<2))

			{

				ans.push_back(j);

				tmp--;

			}

			if (ans.size()==2) break;

		}

		if (ans.size()!=2) continue;

		ll now=1ll*ans[0]*ans[1]/gcd(ans[0],ans[1]);

		if (now<lcm)

		{

			lcm=now;val1=ans[0];val2=ans[1];

		}

	}

	ll pos1=0,pos2=0;

	rep(i,1,n)

	{

		if ((!pos1) && (a[i]==val1)) pos1=i;

		else if ((!pos2) && (a[i]==val2)) pos2=i;

	}

	if (pos1>pos2) swap(pos1,pos2);

	printf("%lld %lld",pos1,pos2);

	return 0;

}

codeforces 1120D Power Tree

如果不要输出方案的话那就可以大力\(dp\)，记\(dp[u][0/1]\)为控制以\(u\)为根的子树的最小代价，其中\(0\)表示不选\(u\)的祖先\(1\)表示选，考虑\(u\)的儿子是不需要选祖先或者某一个需要祖先来进行转移

然而似乎输出方案很难写。。。弃了弃了看题解

将控制一个点的操作转化到树的dfs序上，也就是控制了一段区间，注意到这个\(dfs\)序我们只需要保留叶子结点

为了转化区间操作，我们将这个\(dfs\)转化成差分序列，即一次对\([l,r]\)的操作可以看做是在\(l\)加上一个数同时在\(r+1\)上减去一个数

考虑题目是要求最后能使得整个序列都变成\(0\)，等价于让这个差分序列变成\(0\)

也就是说对于每个点我们都希望有一条能单独修改它的路径

将差分序列的每个位置看成是一个点，一次修改看成是一条边，跑kruskal即可

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

#define maxd 1000000007

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

struct sqnode{

	int to,nxt;

}sq[400400];

struct edgenode{

	int u,v,w,id;

}edge[200200];

bool operator <(const edgenode &p,const edgenode &q)

{

	return p.w<q.w;

}

int n,w[200200],all=0,head[200200],l[200200],r[200200],tot=0,tim=0,fa[200200];

bool vis[200200];

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

int find(int x)

{

	if (fa[x]==x) return x;

	fa[x]=find(fa[x]);

	return fa[x];

}

void dfs(int u,int fu)

{

	int i;

	l[u]=maxd;r[u]=0;

	for (i=head[u];i;i=sq[i].nxt)

	{

		int v=sq[i].to;

		if (v==fu) continue;

		dfs(v,u);vis[u]=1;

		l[u]=min(l[u],l[v]);

		r[u]=max(r[u],r[v]);

	}

	if ((!vis[u]) && (u!=1)) {l[u]=(++tim);r[u]=tim;}

	edge[++tot]=(edgenode){l[u],r[u]+1,w[u],u};

}

void add(int u,int v)

{

	all++;sq[all].to=v;sq[all].nxt=head[u];head[u]=all;

}

int main()

{

	n=read();

	rep(i,1,n) w[i]=read();

	rep(i,1,n-1)

	{

		int u=read(),v=read();

		add(u,v);add(v,u);

	}

	memset(vis,0,sizeof(vis));

	dfs(1,0);

	sort(edge+1,edge+1+n);

	ll ans=0;

	rep(i,1,tim+1) fa[i]=i;

	memset(vis,0,sizeof(vis));

	int l=1,r=1;

	for (l=1;l<=n;l=r+1)

	{

		while ((r<n) && (edge[r+1].w==edge[l].w)) r++;

		rep(j,l,r)

		{

			int x=edge[j].u,y=edge[j].v,

				fx=find(x),fy=find(y);

			if (fx!=fy) vis[edge[j].id]=1;

		}

		rep(j,l,r)

		{

			int x=edge[j].u,y=edge[j].v,

				fx=find(x),fy=find(y);

			if (fx!=fy) {fa[fx]=fy;ans+=edge[j].w;}

		}

	}

	int cnt=0;

	rep(i,1,n) if (vis[i]) cnt++;

	printf("%lld %d\n",ans,cnt);

	rep(i,1,n) if (vis[i]) printf("%d ",i);

	return 0;

}

codeforces1137D Cooperative Game

学不来告辞

利用floyd和pollard-rho中的判圈方式，我们让\(0\)号棋子一次走一步，\(1\)号棋子两次走一步，直到两者相遇

我们假设此时\(1\)号棋子走了\(T+x\)步，那么\(0\)号棋子走了\(2(T+x)\)步

且应有\(T+x\equiv 0(mod\ C)\)

因此\(0\)和\(1\)号这两颗棋子再走\(T\)步即可到达终点

且剩下的\(8\)棵棋子需要走一条链的长度，也是\(T\)步

于是我们可以在\(2x+3T\)的步数内完成这一过程，由于\(x<C\)，所以总步数小于\(3(T+C)\)

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

#define maxd 1000000007

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

char s[20];

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

int get_num()

{

	int ans=read();

	rep(i,1,ans) scanf("%s",s);

	return ans;

}

int main()

{

	while (1)

	{

		printf("next 0\n");fflush(stdout);

		int cnt=get_num();

		printf("next 0 1\n");fflush(stdout);

		cnt=get_num();

		if (cnt==2) break;

	}

	while (1)

	{

		printf("next 0 1 2 3 4 5 6 7 8 9\n");fflush(stdout);

		int cnt=get_num();

		if (cnt==1) break;

	}

	printf("done\n");fflush(stdout);

	return 0;

}

codeforces1151F Sonya and Informatics

数据范围暗示矩乘系列

考虑最原始的\(dp\)，假设序列里有\(z\)个\(0\)，\(n-z\)个\(1\)，目标状态是前\(z\)个均是\(0\)

记\(dp[i][j]\)为前\(i\)位有\(j\)个\(1\)时的方案数，显然答案是\(dp[z][0]\)除上总方案数

在转移的时候\(dp[i][j]\)可能转移到\(j-1,j.j+1\)，具体的有

  • 转移到\(j\)时

    • 前一部分或者后一部分内部的移动，有\(\dbinom{z}{2}+\dbinom{n-z}{2}\)种
    • 前一部分的\(1\)和后一部分的\(1\)相互移动，有\(j*(n-z-j)\)种
    • 前一部分的\(0\)和后一部分的\(0\)相互移动，有\((z-j)*j\)种

  • 转移到\(j-1\)时

    • 前一部分的\(1\)转移到后一部分的\(0\)，有\(j*j\)种

  • 转移到\(j+1\)时

    • 前一部分的\(0\)转移到后一部分的\(1\)，有\((z-j)*(n-z-j)\)种

由于\(dp[i]\)全部至于\(dp[i-1]\)有关，我们维护\(dp[i]\)的矩阵即可

貌似将转移矩阵右乘可以使得它和普通的转移区别不大？

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

#define maxd 1000000007

typedef long long ll;

const double pi=acos(-1.0);

int N,n,k,x[120],zero=0;

struct matrix{

	ll x[120][120];

}ans,a;

matrix mul(matrix a,matrix b)

{

	matrix c;

	rep(i,0,N) rep(j,0,N) c.x[i][j]=0;

	rep(i,0,N)

	{

		rep(j,0,N)

		{

			rep(k,0,N)

			{

				c.x[i][j]=(c.x[i][j]+a.x[i][k]*b.x[k][j])%maxd;

			}

		}

	}

	return c;

}

ll qpow(ll x,ll y)

{

	ll ans=1;

	while (y)

	{

		if (y&1) ans=(ans*x)%maxd;

		x=(x*x)%maxd;

		y>>=1;

	}

	return ans;

}

matrix qpow(matrix a,int y)

{

	matrix ans;

	rep(i,0,N) ans.x[i][i]=1;

	while (y)

	{

		if (y&1) ans=mul(ans,a);

		a=mul(a,a);

		y>>=1;

	}

	return ans;

}

ll inv(ll x) {return qpow(x,maxd-2);}

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

ll C(ll x,ll y)

{

	return (1ll*x*(x-1)/2)%maxd;

}

int main()

{

	n=read();k=read();

	rep(i,1,n) {x[i]=read();zero+=(x[i]==0);}

	int now=0;

	rep(i,1,zero) now+=(x[i]==1);

	N=min(n-zero,zero);

	rep(i,0,N)

	{

		a.x[i][i]=(a.x[i][i]+C(zero,2)+C(n-zero,2))%maxd;

		a.x[i][i]=(a.x[i][i]+1ll*i*(n-zero-i))%maxd;

		a.x[i][i]=(a.x[i][i]+1ll*(zero-i)*i)%maxd;

		if (i) a.x[i][i-1]=(a.x[i][i-1]+1ll*i*i)%maxd;

		if (i<N) a.x[i][i+1]=(a.x[i][i+1]+1ll*(zero-i)*(n-zero-i))%maxd;

	}

	a=qpow(a,k);ans.x[0][now]=1;

	ans=mul(ans,a);

	ll final=ans.x[0][0];

	final=(final*inv(qpow(C(n,2),k)))%maxd;

	printf("%lld",final);

	return 0;

}

codeforces 1117G. Recursive Queries

考虑\(f(l,r)\)的实际意义，可以被看做是遍历一遍这个区间找到最大值后分治成两个子问题，求最后的遍历元素数

考虑位置\(i\)上的元素，即左边第一个比它大的数的位置是\(l_i\)，右边第一个比它大的数是\(r_i\)

那么\(i\)只会在\([l_i+1,r_i-1]\)这个区间才会被删去，结合原来区间\([L,R]\)知答案就是所有位置的区间长度之和，即\(\sum_{i=l}^rmin(R.r_i-1)-max(L,l_i+1)+1\)

最简单的思路就是使用线段树维护这个答案，区间加\([l_i+1,r_i-1]\)即可，但是会出现\(L\)左边的点所在的区间对答案产生影响的情况

此时我们将原来的区间拆成\([l_i+1,i]\)和\([i+1,r_i-1]\)两个区间，这样的话把原来的双向区间变成了单向，离线维护即可

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

#define maxd 1000000007

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

int n,q,ql[1001000],qr[1001000],l[1001000],r[1001000],a[1001000];

ll seg[8008000],tag[8008000],ans[1001000];

vector<pair<int,int> > lq[1001000],rq[1001000];

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

void build(int id,int l,int r)

{

	seg[id]=0;tag[id]=0;

	if (l==r) return;

	int mid=(l+r)>>1;

	build(id<<1,l,mid);

	build(id<<1|1,mid+1,r);

}

void pushdown(int id,int l,int r)

{

	if (tag[id])

	{

		tag[id<<1]+=tag[id];

		tag[id<<1|1]+=tag[id];

		int mid=(l+r)>>1;

		seg[id<<1]+=tag[id]*(mid-l+1);

		seg[id<<1|1]+=tag[id]*(r-mid);

		tag[id]=0;

	}

}

void modify(int id,int l,int r,int nowl,int nowr)

{

	pushdown(id,l,r);

	if ((l>=nowl) && (r<=nowr))

	{

		seg[id]+=(r-l+1);tag[id]++;

		return;

	}

	int mid=(l+r)>>1;

	if (nowl<=mid) modify(id<<1,l,mid,nowl,nowr);

	if (nowr>=mid+1) modify(id<<1|1,mid+1,r,nowl,nowr);

	seg[id]=seg[id<<1]+seg[id<<1|1];

}

ll query(int id,int l,int r,int nowl,int nowr)

{

	pushdown(id,l,r);

	if ((l>=nowl) && (r<=nowr)) return seg[id];

	int mid=(l+r)>>1;ll ans=0;

	if (nowl<=mid) ans+=query(id<<1,l,mid,nowl,nowr);

	if (nowr>=mid+1) ans+=query(id<<1|1,mid+1,r,nowl,nowr);

	return ans;

}

int main()

{

	n=read();q=read();

	rep(i,1,n) a[i]=read();

	a[0]=maxd;a[n+1]=maxd;

	rep(i,1,n)

	{

		l[i]=i-1;

		while (a[l[i]]<=a[i]) l[i]=l[l[i]];

	}

	per(i,n,1)

	{

		r[i]=i+1;

		while (a[r[i]]<=a[i]) r[i]=r[r[i]];

	}

	rep(i,1,q) ql[i]=read();

	rep(i,1,q) qr[i]=read();

	rep(i,1,q)

	{

		lq[qr[i]].push_back(make_pair(ql[i],i));

		rq[ql[i]].push_back(make_pair(qr[i],i));

	}

	build(1,1,n);

	rep(i,1,n)

	{

		modify(1,1,n,l[i]+1,i);

		int len=lq[i].size();

		rep(j,0,len-1) ans[lq[i][j].second]=query(1,1,n,lq[i][j].first,i);

	}

	build(1,1,n);

	per(i,n,1)

	{

		if (i+1<r[i]) modify(1,1,n,i+1,r[i]-1);

		int len=rq[i].size();

		rep(j,0,len-1) ans[rq[i][j].second]+=query(1,1,n,i+1,rq[i][j].first);

	}

	rep(i,1,q) printf("%lld ",ans[i]);

	return 0;

}

codeforces 1137C. Museums Tour

考虑拆点，将一个博物馆按照一个星期的天数拆成\(d\)个点，一条边\(u->v\)对应着连接\((u,j)\)和\((v,j+1)\)（\(j\)表示是这个星期的的第几天）

然后按照正常剧本我们应该开始\(tarjan\)缩点然后在\(DAG\)上跑\(dp\)，不过先停一下，想一下这个问题：缩完点之后会不会重复计数呢？即在联通块\(x\)中有一个合法点\((u,i)\)，会不会在\(x\)可以到达的某个联通块\(y\)中存在另一个合法点\((u,j)\)呢？

我们设\((u,i)\)能到达\((u,j)\)，实际意义就是在点\(u\)可以经过\(i-j\)天的时间走一个环，记这个差为\(d\)，那么\((u,j)\)经过\(d\)天之后应该也能走早\((u,j+d)\)，一直迭代下去一定会回到\((u,i)\)

综上所述，对于从同一个点拆出来的点，如果其中一个能到达另一个，那么另一个也能走回来，即它们属于同一个\(scc\)中

故暴力\(dp\)即可，利用\(tarjan\)是拓扑序的倒序可以省一个\(toposort\)而直接\(dp\)

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<stack>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

#define maxd 1000000007

typedef long long ll;

const int N=5001000;

const double pi=acos(-1.0);

struct node{

	int to,nxt;

}sq1[N],sq2[N];

int n,m,d,head1[N],head2[N],all1=0,all2=0,tot=0,tim=0,dfn[N],low[N],

	dp[N],cnt[N],col[N],vis[N];

char s[100100][60];

bool in[N];

stack<int> sta;

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

int id(int x,int y)

{

	return x+(y-1)*n;

}

void add1(int u,int v)

{

	all1++;sq1[all1].to=v;sq1[all1].nxt=head1[u];head1[u]=all1;

}

void add2(int u,int v)

{

	all2++;sq2[all2].to=v;sq2[all2].nxt=head2[u];head2[u]=all2;

}

void tarjan(int u)

{

	dfn[u]=low[u]=(++tim);

	sta.push(u);in[u]=1;

	int i;

	for (i=head1[u];i;i=sq1[i].nxt)

	{

		int v=sq1[i].to;

		if (!dfn[v])

		{

			tarjan(v);

			low[u]=min(low[u],low[v]);

		}

		else if (in[v]) low[u]=min(low[u],dfn[v]);

	}

	if (dfn[u]==low[u])

	{

		tot++;

		while (1)

		{

			int v=sta.top();sta.pop();

			col[v]=tot;in[v]=0;

			if (u==v) break;

		}

	}

}

int main()

{

	n=read();m=read();d=read();

	rep(i,1,m)

	{

		int u=read(),v=read();

		rep(j,1,d) add1(id(u,j),id(v,j%d+1));

	}

	rep(i,1,n*d) if (!dfn[i]) tarjan(i);

	rep(i,1,n) scanf("%s",s[i]+1);

	rep(i,1,n)

	{

		rep(j,1,d)

		{

			int tmp=id(i,j);

			if ((s[i][j]=='1') && (vis[col[tmp]]<i))

			{

				vis[col[tmp]]=i;cnt[col[tmp]]++;

			}

		}

	}

	rep(i,1,n*d)

	{

		int j;

		for (j=head1[i];j;j=sq1[j].nxt)

		{

			int v=sq1[j].to;

			if (col[i]!=col[v]) add2(col[i],col[v]);

		}

	}

	rep(i,1,tot)

	{

		int j;

		for (j=head2[i];j;j=sq2[j].nxt)

		{

			int v=sq2[j].to;

			dp[i]=max(dp[i],dp[v]);

		}

		dp[i]+=cnt[i];

	}

	printf("%d",dp[col[id(1,1)]]);

	return 0;

}

codeforces 1111D. Destroy the Colony

首先这个\(q\leq 10^5\)就是假的，本质不同的询问个数一共有\(26*26\)种考虑将其全部处理出来

首先我们将排列转成组合，对于每一种集合的选定方式，它对应着的排列由可重复的排列公式知为\(\frac{(\frac{n}{2})^2}{\sum cnt_i!}\)(\(cnt_i\)表示当前集合中的元素个数)

那么转化为从给定元素中选出\(\frac{n}{2}\)个元素，满足\(x\)和\(y\)同时存在或不存在且所有同种元素要么全都存在要么全都不存在

先忽略第一个条件，就是一个01背包

再考虑有第一个条件，我们可以看做是没有这两种物品，然后选出\(\frac{n}{2}\)个元素，然后将其\(*2\)（作前一半还是后一半）即可

取消这两种物品的方案数可以使用退背包完成，具体的记原来的方案为\(f_i\)，那么没有种类\(x\)的方案数\(g_i\)可以看做无法从\(f_{i-cnt_x}\)转移到\(f_i\)，故\(g_i=f_{i-cnt_x}\)

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

#define maxd 1000000007

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

int n,cnt[100100],q;

ll dp[100100],fac[100100],invfac[100100],same[100][100],tmp[100100];

char s[100100];

int read()

{

    int x=0,f=1;char ch=getchar();

    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

    return x*f;

}

ll qpow(ll x,ll y)

{

    ll ans=1;

    while (y)

    {

        if (y&1) ans=(ans*x)%maxd;

        x=(x*x)%maxd;

        y>>=1;

    }

    return ans;

}

int main()

{

    scanf("%s",s+1);n=strlen(s+1);fac[0]=1;invfac[0]=1;

    rep(i,1,n)

    {

        if ((s[i]>='a') && (s[i]<='z')) cnt[s[i]-'a'+1]++;

        else cnt[s[i]-'A'+1+26]++;

        fac[i]=(fac[i-1]*i)%maxd;

    }

    invfac[n]=qpow(fac[n],maxd-2);

    per(i,n-1,1) invfac[i]=invfac[i+1]*(i+1)%maxd;

    dp[0]=1;

    rep(i,1,52)

    {

        if (!cnt[i]) continue;

        per(j,n/2,cnt[i])

            dp[j]=(dp[j]+dp[j-cnt[i]])%maxd;

    }

    rep(i,1,52)

    {

        rep(j,i,52)

        {

            rep(k,0,n/2) tmp[k]=dp[k];

            rep(k,cnt[i],n/2) tmp[k]=(tmp[k]-tmp[k-cnt[i]]+maxd)%maxd;

            if (i!=j)

                rep(k,cnt[j],n/2) tmp[k]=(tmp[k]-tmp[k-cnt[j]]+maxd)%maxd;

            same[i][j]=tmp[n/2];

        }

    }

    ll w=fac[n/2]*fac[n/2]%maxd;

    rep(i,1,52) w=w*invfac[cnt[i]]%maxd;

    q=read();

    while (q--)

    {

        int x=read(),y=read();

        if ((s[x]>='a') && (s[x]<='z')) x=s[x]-'a'+1;

        else x=s[x]-'A'+1+26;

        if ((s[y]>='a') && (s[y]<='z')) y=s[y]-'a'+1;

        else y=s[y]-'A'+1+26;

        if (x>y) swap(x,y);

        printf("%lld\n",w*same[x][y]*2%maxd);

    }

    return 0;

}

codeforces 1111E. Tree

看起来一脸虚树的样子但是我不费啊qwq

一般的tree dp是记\(dp[u][i]\)表示以\(u\)为根的子树分成\(i\)组的方案数，然后你发现这颗树连根都不确定，使用虚树并不是很容易维护（其实就是我不费）

那么考虑这只是序列上的问题呢？记\(dp[i][j]\)为前\(i\)个数分成\(j\)组的方案数，那么\(dp[i][j]=dp[i-1][j]*(j-f[i])+dp[i-1][j-1]\)，\(f[i]\)表示\(i\)前面的数中有多少个不能和\(i\)分在一起

注意到这么\(dp\)的一个问题是我们要确定一个合适的\(dp\)顺序使得\(i\)只会被它前面的数所影响

首先为了把树上问题转化到序列上我们肯定是会考虑\(dfs\)序的，考虑\(f[i]\)只代表\(i\)到根之间不能和\(i\)共处一组的点的个数，那么这个可以直接树剖求解，故我们只要使得在我们确定的\(dp\)顺序中儿子节点不会出现在根节点之前即可

这看起来可以用\(LCT\)，实际上我们直接按照\(f[i]\)排序即可因为祖先节点的\(f\)一定比儿子节点的小

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

#define maxd 1000000007

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

struct node{

	int to,nxt;

}sq[200200];

int all=0,head[100100],n,q,a[101000],f[101000],seg[800400],dep[100100],

	fa[100100],son[100100],siz[100100],tp[100100],tot=0,dfn[100100];

ll dp[2][100100];

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

void add(int u,int v)

{

	all++;sq[all].to=v;sq[all].nxt=head[u];head[u]=all;

}

void dfs1(int u,int fu)

{

	dep[u]=dep[fu]+1;fa[u]=fu;siz[u]=1;

	int i,maxson=0;

	for (i=head[u];i;i=sq[i].nxt)

	{

		int v=sq[i].to;

		if (v==fu) continue;

		dfs1(v,u);

		siz[u]+=siz[v];

		if (siz[v]>maxson) {maxson=siz[v];son[u]=v;}

	}

}

void dfs2(int u,int tpu)

{

	tp[u]=tpu;dfn[u]=(++tot);

	if (!son[u]) return;

	dfs2(son[u],tpu);

	int i;

	for (i=head[u];i;i=sq[i].nxt)

	{

		int v=sq[i].to;

		if ((v==fa[u]) || (v==son[u])) continue;

		dfs2(v,v);

	}

}

void modify(int id,int l,int r,int pos,int val)

{

	seg[id]+=val;

	if (l==r) return;

	int mid=(l+r)>>1;

	if (pos<=mid) modify(id<<1,l,mid,pos,val);

	else modify(id<<1|1,mid+1,r,pos,val);

}

int query(int id,int l,int r,int nowl,int nowr)

{

	if ((l>=nowl) && (r<=nowr)) return seg[id];

	int ans=0,mid=(l+r)>>1;

	if (nowl<=mid) ans+=query(id<<1,l,mid,nowl,nowr);

	if (nowr>=mid+1) ans+=query(id<<1|1,mid+1,r,nowl,nowr);

	return ans;

}

int query_range(int u,int v)

{

	int ans=0;

	while (tp[u]!=tp[v])

	{

		if (dep[tp[u]]<dep[tp[v]]) swap(u,v);

		ans+=query(1,1,n,dfn[tp[u]],dfn[u]);

		u=fa[tp[u]];

	}

	if (dep[u]>dep[v]) swap(u,v);

	ans+=query(1,1,n,dfn[u],dfn[v]);

	return ans;

}

void init()

{

	n=read();q=read();

	rep(i,1,n-1)

	{

		int u=read(),v=read();

		add(u,v);add(v,u);

	}

	dfs1(1,0);dfs2(1,1);

}

void work()

{

	while (q--)

	{

		int k=read(),m=read(),rt=read();

		rep(i,1,k)

		{

			a[i]=read();

			modify(1,1,n,dfn[a[i]],1);

		}

		int flag=0;

		rep(i,1,k)

		{

			f[i]=query_range(a[i],rt)-1;

			if (f[i]>=m) {flag=1;break;}

		}

		rep(i,1,k) modify(1,1,n,dfn[a[i]],-1);

		if (flag) {puts("0");continue;}

		sort(f+1,f+1+k);

		int now=1,pre=0;

		dp[0][0]=1;

		rep(i,1,m) dp[0][i]=0;

		rep(i,1,k)

		{

			rep(i,0,m) dp[now][i]=0;

			per(j,min(i,m),0)

			{

				if (j<=f[i]) dp[now][j]=0;

				else dp[now][j]=(dp[pre][j]*(j-f[i])+dp[pre][j-1])%maxd;

			}

			now^=1;pre^=1;

		}

		ll ans=0;

		rep(i,1,m) ans=(ans+dp[pre][i])%maxd;

		printf("%lld\n",ans);

	}

}

int main()

{

	init();

	work();

	return 0;

}

codeforces 765F Souvenirs

将询问离线，记\(f_i\)为\(i\)为左端点时的答案，从左到右遍历右端点\(j\)，每次更新\(1\text~j-1\)的答案，肯定不能暴力更新

考虑使用线段树维护\(f\)数组，更新时沿途记录当前的最优答案\(now\)

记当前更新的区间为\([l,r]\)，如果这个区间不存在\(a_j-now\text~a_j+now\)的数的话就说明当前的\(a_j\)不会对该区间的答案产生影响，可以不用继续更新下去

但是我们又注意到\(\forall p<q\)，应该有\(f_p\leq f_q\)，因为\([p,n]\)肯定包含了\([q,n]\)，故更新时应先更新右区间再更新左区间防止\(now\)的值出现问题，可以证明此方法的时间复杂度是\(O(nlogn^2)\)的

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

#define maxd 1000000007

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

struct node{

	int ans;

	vector<int> num;

}seg[800800];

struct qnode{

	int l,r,id;

}q[300300];

bool operator<(const qnode &p,const qnode &q)

{

	return p.r<q.r;

}

int n,Q,a[100100],ans[300300];

vector<int>::iterator it;

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

void build(int id,int l,int r)

{

	rep(i,l,r) seg[id].num.push_back(a[i]);

	sort(seg[id].num.begin(),seg[id].num.end());

	seg[id].ans=maxd;

	if (l==r) return;

	int mid=(l+r)>>1;

	build(id<<1,l,mid);

	build(id<<1|1,mid+1,r);

	rep(i,0,r-l-1) seg[id].ans=min(seg[id].ans,seg[id].num[i+1]-seg[id].num[i]);

}

int query(int id,int l,int r,int ql,int qr)

{

	if ((l>=ql) && (r<=qr)) return seg[id].ans;

	int mid=(l+r)>>1,ans=maxd;

	if (ql<=mid) ans=min(ans,query(id<<1,l,mid,ql,qr));

	if (qr>=mid+1) ans=min(ans,query(id<<1|1,mid+1,r,ql,qr));

	return ans;

}

void modify(int id,int l,int r,int qr,int val,int &nowans)

{

	if (l==r)

	{

		seg[id].ans=min(seg[id].ans,abs(seg[id].num[0]-val));

		nowans=min(nowans,seg[id].ans);

		return;

	}

	it=lower_bound(seg[id].num.begin(),seg[id].num.end(),val);

	if (((it==seg[id].num.begin()) || (*(it-1)<=val-nowans)) &&

		((it==seg[id].num.end()) || (*it>=val+nowans)))

	{

		nowans=min(nowans,query(id,l,r,l,qr));

		return;

	}

	int mid=(l+r)>>1;

	if (qr>=mid+1) modify(id<<1|1,mid+1,r,qr,val,nowans);

	modify(id<<1,l,mid,qr,val,nowans);

	seg[id].ans=min(seg[id<<1].ans,seg[id<<1|1].ans);

}

int main()

{

	n=read();

	rep(i,1,n) a[i]=read();

	build(1,1,n);

	Q=read();

	rep(i,1,Q) {q[i].l=read();q[i].r=read();q[i].id=i;}

	sort(q+1,q+1+Q);

	int nowr=1;

	rep(i,1,Q)

	{

		while (nowr<q[i].r) {int tmp=maxd;modify(1,1,n,nowr,a[nowr+1],tmp);nowr++;}

		ans[q[i].id]=query(1,1,n,q[i].l,q[i].r);

	}

	rep(i,1,Q) printf("%d\n",ans[i]);

	return 0;

}

codeforces 1155E Guess the Root

不是很懂这题为什么要出成交互，感觉比即时战略还不像交互

询问\([0,10]\)的值，拉格朗日插值得到这个多项式，再枚举\([11,maxd-1]\)得到其相应的值判断是否为\(0\)即可

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

#define maxd 1000003

typedef long long ll;

const int N=200000;

const double pi=acos(-1.0);

ll x[20],fac[N+100],invfac[N+100];

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

int query(int a)

{

	printf("? %d\n",a);fflush(stdout);

	x[a]=read();

	return (x[a]==0);

}

void answer(int ans)

{

	printf("! %d\n",ans);fflush(stdout);

}

int getval(int a)

{

	ll ans=0;

	rep(i,0,10)

	{

		ll now=x[i];

		rep(j,0,10) if (i!=j) now=(now*(a-j))%maxd;

		now=now*invfac[i]*invfac[10-i]%maxd;

		if ((10-i)&1) ans=(ans+maxd-now)%maxd;

		else ans=(ans+now)%maxd;

	}

	return ans;

}

ll qpow(ll x,ll y)

{

	ll ans=1;

	while (y)

	{

		if (y&1) ans=(ans*x)%maxd;

		x=(x*x)%maxd;

		y>>=1;

	}

	return ans;

}

int main()

{

	fac[0]=1;invfac[0]=1;

	rep(i,1,N) fac[i]=(fac[i-1]*i)%maxd;

	invfac[N]=qpow(fac[N],maxd-2);

	per(i,N-1,1) invfac[i]=(invfac[i+1]*(i+1))%maxd;

	rep(i,0,10)

	{

		bool zero=query(i);

		if (zero)

		{

			answer(i);

			return 0;

		}

	}

	rep(i,11,maxd-1)

	{

		int now=getval(i);

		if (!now) {answer(i);return 0;}

	}

	answer(-1);

	return 0;

}

codeforces 1146E. Hot is Cold

线段树维护每个数是否需要取其相反数

分类讨论

  • \(s\)为\(>\)时

    • 若\(x\geq0\)
      • 那么对于原来的值为\([x+1,N]\)的值而言，无论其是否取反，最后它们的符号一定是负数，即一定取反
      • 对\([-N,-x-1]\)而言，它们一定保持负数的值，故一定不取反
      • 剩下的值不变
    • 若\(x<0\)
      • 对\([-x,N]\)，一定为负，故一定取反
      • 对\([-N,x]\)，一定为负，故一定不取反
      • 对\([x+1,-x-1]\)，按照要求进行反转即可

  • \(s\)为\(<\)时

    • 若\(x\leq 0\)
      • 对\([-N,x-1]\)，它们一定为正，故一定取反
      • 对\([-x+1,N]\)，它们一定为正，故一定不取反
    • 若\(x>0\)
      • 对\([x,N]\)，一定为正，一定不取反
      • 对\([-N,-x]\)，一定为正，一定取反
      • 对\([-x+1,x-1]\)，按照要求进行反转即可

线段树维护区间赋值和区间反转即可

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define rep(i,a,b) for (int i=a;i<=b;i++)

#define per(i,a,b) for (int i=a;i>=b;i--)

#define maxd 1000000007

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

int n,q,a[100100],seg[1700000],rev[1700000],tag[1700000];

char s[10];

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

void pushdown(int id,int l,int r)

{

	if (tag[id]!=-1)

	{

		seg[id<<1]=tag[id];

		seg[id<<1|1]=tag[id];

		tag[id<<1]=tag[id];

		tag[id<<1|1]=tag[id];

		rev[id<<1]=0;rev[id<<1|1]=0;

		tag[id]=-1;

	}

	if (rev[id])

	{

		rev[id<<1]^=1;rev[id<<1|1]^=1;

		seg[id<<1]^=1;seg[id<<1|1]^=1;

		rev[id]=0;

	}

}

void modify_val(int id,int l,int r,int ql,int qr,int val)

{

	if (ql>qr) return;

	pushdown(id,l,r);

	if ((l>=ql) && (r<=qr))

	{

		seg[id]=val;tag[id]=val;

		return;

	}

	int mid=(l+r)>>1;

	if (ql<=mid) modify_val(id<<1,l,mid,ql,qr,val);

	if (qr>mid) modify_val(id<<1|1,mid+1,r,ql,qr,val);

}

void modify_rev(int id,int l,int r,int ql,int qr)

{

	if (ql>qr) return;

	pushdown(id,l,r);

	if ((l>=ql) && (r<=qr))

	{

		seg[id]^=1;rev[id]=1;

		return;

	}

	int mid=(l+r)>>1;

	if (ql<=mid) modify_rev(id<<1,l,mid,ql,qr);

	if (qr>mid) modify_rev(id<<1|1,mid+1,r,ql,qr);

}

int query(int id,int l,int r,int pos)

{

	pushdown(id,l,r);

	if (l==r) return seg[id];

	int mid=(l+r)>>1;

	if (pos<=mid) return query(id<<1,l,mid,pos);

	else return query(id<<1|1,mid+1,r,pos);

}

int main()

{

	n=read();q=read();

	rep(i,1,n) a[i]=read();

	memset(tag,-1,sizeof(tag));

	while (q--)

	{

		scanf("%s",s);int x=read();

		if (s[0]=='>')

		{

			if (x>=0)

			{

				modify_val(1,-N,N,x+1,N,1);

				modify_val(1,-N,N,-N,-x-1,0);

			}

			else

			{

				modify_val(1,-N,N,-x,N,1);

				modify_val(1,-N,N,-N,x,0);

				modify_rev(1,-N,N,x+1,-x-1);

			}

		}

		else

		{

			if (x<=0)

			{

				modify_val(1,-N,N,-N,x-1,1);

				modify_val(1,-N,N,-x+1,N,0);

			}

			else

			{

				modify_val(1,-N,N,x,N,0);

				modify_val(1,-N,N,-N,-x,1);

				modify_rev(1,-N,N,-x+1,x-1);

			}

		}

	}

	rep(i,1,n)

	{

		if (query(1,-N,N,a[i])) a[i]*=-1;

		printf("%d ",a[i]);

	}

	return 0;

}

codeforces 1146F. Leaf Partition

记\(dp_{u,0/1}\)表示以\(u\)为根的子树，不选/选父亲的方案数，最终答案就是\(dp_{1,0}\)

对每一个点再记\(f_{i,0/1/2}\)表示\(i\)节点不选儿子/选一个儿子/选两个以上儿子的方案

对于一个叶子结点，很明显\(dp_{u,0}=dp_{u,1}=1\)

对于一个非叶子节点，若\(f\)数组已经计算好了，我们有\(dp_{u,0}=f_{u,0}+f_{u,2},dp_{u,1}=f_{u,1}+f_{u,2}\)。原因如下：

1）当一个点不选儿子的时候，它不可能出现在所有叶子集合中的最小联通子图

2）当一个点只选一个儿子的时候，父亲节点必然起到了连接两个叶子结点的作用，否则根据最小联通子图的定义我们是不会选父亲节点的

3）当一个点选了两个以上的儿子时，它本身就可以构成一个最小联通子图，他还可以连接其它的叶子构成新的联通子图，所以对两边都有贡献

故问题转为如何求\(f\)

考虑某个点\(u\)的一个儿子\(v\)，它对父亲的儿子数量至多有\(1\)的贡献，暴力枚举\(dp\)和\(f\)的第二维进行转移即可

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define fir first

#define sec second

#define rep(i,a,b) for (register int i=a;i<=b;i++)

#define per(i,a,b) for (register int i=a;i>=b;i--)

#define maxd 998244353

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

int n;

ll dp[200200][2];

vector<int> sq[200200];

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

void dfs(int u)

{

	int len=sq[u].size();

	ll f[4],tmp[4];

	if (!len) {dp[u][0]=1;dp[u][1]=1;return;}

	f[0]=1;f[1]=0;f[2]=0;

	rep(i,0,len-1)

	{

		int v=sq[u][i];

		dfs(v);

		memset(tmp,0,sizeof(tmp));

		rep(j,0,2)

			rep(k,0,1)

			{

				int now=min(j+k,2);

				tmp[now]=(tmp[now]+f[j]*dp[v][k]%maxd)%maxd;

			}

		f[0]=tmp[0];f[1]=tmp[1];f[2]=tmp[2];

	}

	dp[u][0]=(f[0]+f[2])%maxd;

	dp[u][1]=(f[1]+f[2])%maxd;

}

int main()

{

	n=read();

	rep(i,2,n)

	{

		int u=read();

		sq[u].push_back(i);

	}

	dfs(1);

	printf("%lld",dp[1][0]);

	return 0;

}

codeforces 1149D. Abandoning Roads

考虑\(kruskal\)的过程：先加入边权较小的边，再加入边权较大的边。我们依照这一过程，先加入这些边权较小的边，这样原图就形成了若干个联通块，很明显在同一个联通块中的点连边是不会用到边权大的边的

根据这一点我们就有一个状压+最短路的思路：\(dis[v][sta]\)表示点\(1\)到点\(v\)且经过的联通块的状态是\(sta\)时的方案数，但是这样的话点个规模达到了\(O(n2^n)\)，无法接受

考虑减少状压的状态数，那么就要寻找哪一些信息是不需要记录的。考虑一个联通块的大小对最短路转移的影响，当块的大小\(\leq 3\)时，我们不可能从一个联通块中的一点出发，沿着边权较大的边，走回这个联通块，因为从某个联通块走出去又走回来至少会走两条边权较大的边（记大边权为\(b\)，小边权为\(a\)），即从外面走的话至少需要走\(2b\)的权值，而直接从联通块内部走的话至多走\(2a\)的权值，故我们的最短路转移时一定不会重复遍历一个大小\(\leq 3\)的联通块，这可以帮助减少状压信息，规模被降至\(O(n2^{\frac{n}{4}})\)，可以接受

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define sqr(x) (x)*(x)

#define fir first

#define sec second

#define rep(i,a,b) for (register int i=a;i<=b;i++)

#define per(i,a,b) for (register int i=a;i>=b;i--)

#define maxd 1000000007

#define eps 1e-6

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

struct hnode{

	int u,dis,s;

};

bool operator <(const hnode &p,const hnode &q)

{

	return p.dis>q.dis;

}

priority_queue<hnode> q;

struct node{

	int to,nxt,cost;

}sq[20020];

int all=0,head[10010];

int n,m,col[100],dis[80][150000],cnt=0,fa[100],siz[100],a,b;

bool vis[75][150000];

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

void add(int u,int v,int w)

{

	all++;sq[all].to=v;sq[all].nxt=head[u];sq[all].cost=w;head[u]=all;

}

int find(int x)

{

	if (fa[x]==x) return fa[x];

	fa[x]=find(fa[x]);

	return fa[x];

}

int main()

{

	n=read();m=read();a=read();b=read();

	rep(i,1,n) {fa[i]=i;siz[i]=1;}

	rep(i,1,m)

	{

		int u=read(),v=read(),w=read();

		add(u,v,w);add(v,u,w);

		if (w==a)

		{

			int fx=find(u),fy=find(v);

			if (fx!=fy)

			{

				fa[fx]=fy;siz[fy]+=siz[fx];

			}

		}

	}

	memset(col,-1,sizeof(col));

	rep(i,1,n)

	{

		if ((col[i]==-1) && (siz[find(i)]>3))

		{

			int fx=find(i);

			rep(j,1,n)

				if (find(j)==fx) col[j]=cnt;

			cnt++;

		}

	}

	rep(i,1,n)

		rep(j,0,(1<<cnt)) dis[i][j]=maxd;

	if (col[1]!=-1) {q.push((hnode){1,0,1<<col[1]});dis[1][1<<col[1]]=0;}

	else {q.push((hnode){1,0,0});dis[1][0]=0;}

	while (!q.empty())

	{

		hnode now=q.top();q.pop();

		if (vis[now.u][now.s]) continue;

		vis[now.u][now.s]=1;

		int i;

		for (i=head[now.u];i;i=sq[i].nxt)

		{

			int v=sq[i].to;

			if (sq[i].cost==a)

			{

				if (dis[now.u][now.s]+sq[i].cost<dis[v][now.s])

				{

					dis[v][now.s]=dis[now.u][now.s]+sq[i].cost;

					q.push((hnode){v,dis[v][now.s],now.s});

				}

			}

			else

			{

				if ((find(now.u)==find(v)) || ((col[v]!=-1) && ((now.s>>col[v])&1))) continue;

				int tmp=now.s;

				if (col[v]!=-1) tmp|=(1<<col[v]);

				if (dis[now.u][now.s]+sq[i].cost<dis[v][tmp])

				{

					dis[v][tmp]=dis[now.u][now.s]+sq[i].cost;

					q.push((hnode){v,dis[v][tmp],tmp});

				}

			}

		}

	}

	rep(i,1,n)

	{

		int ans=maxd;

		rep(j,0,(1<<cnt)) ans=min(ans,dis[i][j]);

		printf("%d ",ans);

	}

	return 0;

}

codeforces 1149C Tree Generator™

一看数据这么大就知道要上数据结构

我们扩充这个括号序列，在每个括号的右侧记录当前所在的节点编号，如下面这棵树我们记做 \(1(2(3)2(4)2)1(5)1\)

codeforces选做

首先，如果我们把\((\)看做\(+1\)，\()\)看做\(-1\)，那么对于数字序列的某一个数\(x\)，它的\(dep\)即为该数所在的序列之前的所有括号的对应数之和，这个由操作定义不难得到

对于我们扩充后的序列，我们取下一个区间\([l,r]\)，注意到节点\(l\)和节点\(r\)的\(lca\)一定在\([l,r]\)中，并且是该区间的所有节点中深度最小的（否则我们的\()\)这个返回操作变得毫无意义）

我们考虑直径是什么，树的直径就是找到两个点使得\(dep_u+dep_v-2*dep_{lca}\)尽可能的大，这个东西映射到括号序列上，其实就是要找到一个三元组\((x,y,z)\)使得\(dep_x+dep_z-2*dep_y\)，因为当\(x、z\)确定时使得该式的值最大的\(y\)就是\(x,z\)的\(lca\)

再将这个式子转化一下：\((dep_z-dep_y)-(dep_y-dep_x)\)，所以我们可以考虑通过维护区间内\(dep_y-dep_x\)的最大值来得到答案，而每一个\(dep\)其实就是一段区间和，于是可以利用最大子段和问题的思想，线段树维护一段区间的最大/小的前/后缀和，前/后缀最大差值，整体最大差值、和以及区间内的最大差值（即答案）

具体实现时注意\(pushup\)，详细细节见代码

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define lowbit(x) (x)&(-x)

#define sqr(x) (x)*(x)

#define fir first

#define sec second

#define rep(i,a,b) for (register int i=a;i<=b;i++)

#define per(i,a,b) for (register int i=a;i>=b;i--)

#define maxd 1000000007

#define eps 1e-6

typedef long long ll;

const int N=100000;

const double pi=acos(-1.0);

struct segnode{

	int premax,premin,sufmax,sufmin,pred,sufd,sum,d,ans;

}seg[800100];

segnode leafl=(segnode){1,0,1,0,1,1,1,1,1},leafr=(segnode){0,-1,0,-1,1,1,-1,1,1};

int n,q;

char s[200200];

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

segnode pushup(segnode a,segnode b)

{

	segnode c;

	c.premax=max(a.premax,a.sum+b.premax);

	c.premin=min(a.premin,a.sum+b.premin);

	c.sufmax=max(b.sufmax,b.sum+a.sufmax);

	c.sufmin=min(b.sufmin,b.sum+a.sufmin);

	c.pred=max(a.pred,max(b.pred-a.sum,a.d+b.premax));

	c.sufd=max(b.sufd,max(b.d-a.sufmin,b.sum+a.sufd));

	c.d=max(b.d-a.sum,a.d+b.sum);

	c.sum=a.sum+b.sum;

	c.ans=max(max(a.ans,b.ans),max(a.sufd+b.premax,b.pred-a.sufmin));

	return c;

}

void build(int id,int l,int r)

{

	if (l==r)

	{

		if (s[l]=='(') seg[id]=leafl;else seg[id]=leafr;

		return;

	}

	int mid=(l+r)>>1;

	build(id<<1,l,mid);build(id<<1|1,mid+1,r);

	seg[id]=pushup(seg[id<<1],seg[id<<1|1]);

}

void modify(int id,int l,int r,int pos)

{

	if (l==r)

	{

		if (s[l]=='(') seg[id]=leafl;else seg[id]=leafr;

		return;

	}

	int mid=(l+r)>>1;

	if (pos<=mid) modify(id<<1,l,mid,pos);

	else modify(id<<1|1,mid+1,r,pos);

	seg[id]=pushup(seg[id<<1],seg[id<<1|1]);

}

int main()

{

	n=read();q=read();n=(n-1)*2;

	scanf("%s",s+1);

	build(1,1,n);

	printf("%d\n",seg[1].ans);

	while (q--)

	{

		int x=read(),y=read();

		swap(s[x],s[y]);

		modify(1,1,n,x);

		modify(1,1,n,y);

		printf("%d\n",seg[1].ans);

	}

	return 0;

}

codeforces 1174 E. Ehab and the Expected GCD Problem

每次写这种带结论的\(dp\)都显得十分自闭

注意到第一个数固定了以后\(g_i\)所含有的质因子，并且由于排列中包含\(1-n\)中的所有数所以一定存在方案使得\(g_{i+1}\)和\(g_i\)非\(1\)时\(g_{i+1}\)正好是\(g_i\)除上某一个质数

于是问题变成了如何安排排列第\(1\)个数使得它含有的质因子个数最多，记这个数为\(x\)

首先我们认为这个数一定能被写成\(2^a*3^y\)的形式，因为若存在一个质数\(p>4\)使得\(p|x\)，那么将\(x\)改写成\(\frac{x}{p}\times4\)的话更优

接下来还会有\(y\leq 1\)，因为若\(y>1\)必有\(9|x\)，于是和上面一样将\(x\)替代成\(\frac{x}{9}\times 4\)即可更优

所以这样的话\(x\)的值就是唯一确定了的了，可以大力\(dp\)了

记\(dp_{i,j,k}\)表示前\(i\)项，\(g_i=2^j*3^k\)的方案数，同时记录\(f(j,k)\)表示\(1-n\)中\(2^j\times3^k\)的倍数

1）若\(g_i=g_{i-1}\)那么此时填的数就是\(2^j\times3^k\)的倍数，但是已经用了\(i-1\)个，于是\(dp_{i,j,k}+=dp_{i-1,j,k}\times(f(j,k)-(i-1))\)

2）若\(g_i*2=g_{i-1}\)那么此时第\(i\)位的数是\(2^j\times3^k\)的倍数但不是\(2^{j+1}\times 3^k\)的倍数，于是\(dp_{i,j,k}+=dp_{i-1,j+1,k}\times(f(j,k)-f(j+1,k))\)

3）若\(g_i*3=g_{i-1}\)，同上可得\(dp_{i,j,k}+=dp_{i-1,j,k+1}\times(f(j,k)-f(j,k+1))\)

初始化\(dp_{i,a,0}=1\)（\(2^a\leq n<2^{a+1}\)），\(dp_{1,a-1,1}=1\)（\(2^{a-1}*3<n\)）

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<math.h>

#include<algorithm>

#include<vector>

#include<queue>

#include<set>

#include<map>

using namespace std;

typedef long long ll;

#define lowbit(x) (x)&(-x)

#define sqr(x) (x)*(x)

#define rep(i,a,b) for (register int i=a;i<=b;i++)

#define per(i,a,b) for (register int i=a;i>=b;i--)

#define fir first

#define sec second

#define maxd 1000000007

#define eps 1e-8

int n;

ll dp[2][21][2];

int read()

{

	int x=0,f=1;char ch=getchar();

	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

	return x*f;

}

ll calc(int x,int y)

{

	int now=(1<<x);

	if (y) now*=3;

	return n/now;

}

int main()

{

	n=read();

	int a=0,b=0;

	int tmp=1;

	while ((tmp<<1)<=n) {tmp<<=1;a++;}

    tmp>>=1;

	if (tmp*3<=n) dp[1][a-1][1]=1;

	dp[1][a][0]=1;

	int now=0,pre=1;

	rep(i,2,n)

	{

		memset(dp[now],0,sizeof(dp[now]));

		rep(j,0,a)

		{

			rep(k,0,1)

			{

				dp[now][j][k]=(dp[now][j][k]+dp[pre][j][k]*(calc(j,k)-i+1))%maxd;

				if (j!=a)

					dp[now][j][k]=(dp[now][j][k]+dp[pre][j+1][k]*(calc(j,k)-calc(j+1,k)))%maxd;

				if (k!=1)

					dp[now][j][k]=(dp[now][j][k]+dp[pre][j][k+1]*(calc(j,k)-calc(j,k+1)))%maxd;

			}

		}

		now^=1;pre^=1;

	}

	ll ans=(dp[pre][0][0]+maxd)%maxd;

	printf("%lld\n",ans);

	return 0;

}

codeforces 1161D. Palindrome XOR

首先有\(|b|=|s|=n,|a|<n\)，于是可以枚举\(|a|=m\)

那么问题转化成现在有\(n+m\)个\(01\)变量，有相同、不相同、强制赋值三个条件

把这个问题放到图上，两个点之间连边表示限制，用\(0\)表示两者相同，\(1\)表示两者不同；对于强制赋值的条件，我们考虑新建两个节点表示\(0\)和\(1\)，然后将赋值条件转化成相同或不同的条件即可

最后考虑答案计算，当前的图不合法仅当出现了奇环，合法的话单就是\(2^{连通块个数-1}\)，减1是因为\(b\)的首位一定为1

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<vector>

#include<math.h>

#include<queue>

#include<set>

#include<map>

using namespace std;

typedef long long ll;

#define lowbit(x) (x)&(-x)

#define sqr(x) (x)*(x)

#define rep(i,a,b) for (register int i=a;i<=b;i++)

#define per(i,a,b) for (register int i=a;i>=b;i--)

#define maxd 998244353

#define eps 1e-8

const int N=2000;

struct node{

    int to,nxt,cost;

}

sq[200200];

int all=0,head[2020];

void add(int u,int v,int w)

{

    all++;sq[all].to=v;sq[all].nxt=head[u];sq[all].cost=w;head[u]=all;

    all++;sq[all].to=u;sq[all].nxt=head[v];sq[all].cost=w;head[v]=all;

}

int n,tot=0,dis[2020],flag;

ll bin[2020];

char s[2020];

int read()

{

    int x=0,f=1;char ch=getchar();

    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

    return x*f;

}

void dfs(int u,int now)

{

    dis[u]=now;

    int i;

    for (i=head[u];i;i=sq[i].nxt)

    {

        int v=sq[i].to;

        if (dis[v]!=-1)

        {

            if (dis[u]^dis[v]^sq[i].cost) flag=1;

        }

        else dfs(v,now^sq[i].cost);

    }

}

ll work(int m)

{

    all=0;flag=0;tot=0;

    memset(head,0,sizeof(head));

    memset(dis,-1,sizeof(dis));

    rep(i,1,n/2) add(i,n-i+1,0);

    rep(i,1,m/2) add(i+n,m-i+1+n,0);

    rep(i,1,m)

        if (s[i]!='?') add(i,i+n,s[i]-'0');

    rep(i,m+1,n)

        if (s[i]!='?') add(i,n+m+1+(s[i]=='1'),0);

    add(n,n+m+2,0);add(n+m,n+m+2,0);add(n+m+1,n+m+2,1);

    rep(i,1,n+m+2)

        if (dis[i]==-1) {tot++;dfs(i,0);}

    if (flag) return 0;

    else return bin[tot-1];

}

int main()

{

    scanf("%s",s+1);

    n=strlen(s+1);bin[0]=1;

    reverse(s+1,s+1+n);

    rep(i,1,N) bin[i]=(bin[i-1]*2)%maxd;

    ll ans=0;

    rep(i,1,n-1) ans=(ans+work(i))%maxd;

    printf("%lld",ans);

    return 0;

}

codeforces 1161E. Rainbow Coins

首先用两次询问找到\(a_i\)的颜色是否与相邻的颜色相同，这样的话我们可以将整个序列缩成一个新序列，并且新序列相邻块颜色不同，每个块记作\(pos_i\)

接下来再花两次询问找到\(pos_i\)与\(pos_{i+2}\)是否相同，之后直接染色即可

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<vector>

#include<math.h>

#include<queue>

#include<set>

#include<map>

using namespace std;

typedef long long ll;

#define lowbit(x) (x)&(-x)

#define sqr(x) (x)*(x)

#define rep(i,a,b) for (register int i=a;i<=b;i++)

#define per(i,a,b) for (register int i=a;i>=b;i--)

#define mp make_pair

#define fir first

#define sec second

#define maxd 998244353

#define eps 1e-8

int n,tp,pos[100100],ans[100100];

map<pair<int,int>,int> same;

vector<int> a,b,col[4];

char s[100100];

int read()

{

    int x=0,f=1;char ch=getchar();

    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

    return x*f;

}

void query()

{

    int len=a.size();

    if (!len) return;

    printf("Q %d ",len);

    rep(i,0,len-1) printf("%d %d ",a[i],b[i]);

    printf("\n");fflush(stdout);

    scanf("%s",s);

    rep(i,0,len-1)

    {

        same[mp(a[i],b[i])]=s[i]-'0';

        same[mp(b[i],a[i])]=s[i]-'0';

    }

    a.clear();b.clear();

}

void answer()

{

    printf("A");

    rep(i,1,3) printf(" %d",col[i].size());

    puts("");fflush(stdout);

    rep(i,1,3)

    {

        int len=col[i].size();

        rep(j,0,len-1) printf("%d ",col[i][j]);

        puts("");fflush(stdout);

    }

}

int main()

{

    int T=read();

    while (T--)

    {

        n=read();same.clear();

        memset(pos,0,sizeof(pos));

        int i;

        for (i=1;i+1<=n;i+=2)

            {a.push_back(i);b.push_back(i+1);}

        query();

        for (i=2;i+1<=n;i+=2)

            {a.push_back(i);b.push_back(i+1);}

        query();

        int tp=1;

        pos[tp]=1;

        rep(i,2,n)

            if (!same[mp(i-1,i)]) pos[++tp]=i;

        for (i=1;i+2<=tp;i+=4)

            {a.push_back(pos[i]);b.push_back(pos[i+2]);}

        for (i=2;i+2<=tp;i+=4)

            {a.push_back(pos[i]);b.push_back(pos[i+2]);}

        query();

        for (i=3;i+2<=tp;i+=4)

            {a.push_back(pos[i]);b.push_back(pos[i+2]);}

        for (i=4;i+2<=tp;i+=4)

            {a.push_back(pos[i]);b.push_back(pos[i+2]);}

        query();

        ans[1]=1;

        if (tp>1) ans[2]=2;

        rep(i,3,tp)

        {

            if (same[mp(pos[i],pos[i-2])]) ans[i]=ans[i-2];

            else ans[i]=6-ans[i-1]-ans[i-2];

        }

        rep(i,1,3) col[i].clear();

        int now=1;

        rep(i,1,tp)

            while ((now!=pos[i+1]) && (now<=n))

                {col[ans[i]].push_back(now);now++;}

        answer();

    }

    return 0;

}

codeforces 1161F. Zigzag Game

首先肯定会选\(Bob\)因为他的第一次移动不受限制，是真正的先手

要想\(Bob\)必胜其实就是找到这个二分图的一个完美匹配，使得\(Bob\)沿着匹配变移动，而\(Alice\)由于\(Increase\)和\(Decrease\)的限制无法沿着匹配边移动即可

不失一般性，我们假设\(Alice\)选择\(Increase\)且将棋子放在左侧

考虑一个完美匹配如何不合法：仅当完美匹配中存在两条边\((w,x)\)和\((y,z)\)使得\(val(w,x)<val(x,y)<val(y,z)\)，因为这样的话当\(Bob\)走\((w,x)\)，\(Alice\)走\((x,y)\)之后，\(Bob\)由于自身\(Decrease\)的限制而无法走匹配边\((y,z)\)

将从左往右的边视为正权边，从右往左的边视作负权边，那么这就是一个稳定婚姻问题，\(O(n^2)\)找匹配即可

对于其他情况，适当的将边权取负即可

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<vector>

#include<math.h>

#include<queue>

#include<set>

#include<map>

using namespace std;

typedef long long ll;

#define lowbit(x) (x)&(-x)

#define sqr(x) (x)*(x)

#define rep(i,a,b) for (register int i=a;i<=b;i++)

#define per(i,a,b) for (register int i=a;i>=b;i--)

#define mp make_pair

#define fir first

#define sec second

#define maxd 998244353

#define eps 1e-8

int n,tp,pos[100100],ans[100100];

map<pair<int,int>,int> same;

vector<int> a,b,col[4];

char s[100100];

int read()

{

    int x=0,f=1;char ch=getchar();

    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

    return x*f;

}

void query()

{

    int len=a.size();

    if (!len) return;

    printf("Q %d ",len);

    rep(i,0,len-1) printf("%d %d ",a[i],b[i]);

    printf("\n");fflush(stdout);

    scanf("%s",s);

    rep(i,0,len-1)

    {

        same[mp(a[i],b[i])]=s[i]-'0';

        same[mp(b[i],a[i])]=s[i]-'0';

    }

    a.clear();b.clear();

}

void answer()

{

    printf("A");

    rep(i,1,3) printf(" %d",col[i].size());

    puts("");fflush(stdout);

    rep(i,1,3)

    {

        int len=col[i].size();

        rep(j,0,len-1) printf("%d ",col[i][j]);

        puts("");fflush(stdout);

    }

}

int main()

{

    int T=read();

    while (T--)

    {

        n=read();same.clear();

        memset(pos,0,sizeof(pos));

        int i;

        for (i=1;i+1<=n;i+=2)

            {a.push_back(i);b.push_back(i+1);}

        query();

        for (i=2;i+1<=n;i+=2)

            {a.push_back(i);b.push_back(i+1);}

        query();

        int tp=1;

        pos[tp]=1;

        rep(i,2,n)

            if (!same[mp(i-1,i)]) pos[++tp]=i;

        for (i=1;i+2<=tp;i+=4)

            {a.push_back(pos[i]);b.push_back(pos[i+2]);}

        for (i=2;i+2<=tp;i+=4)

            {a.push_back(pos[i]);b.push_back(pos[i+2]);}

        query();

        for (i=3;i+2<=tp;i+=4)

            {a.push_back(pos[i]);b.push_back(pos[i+2]);}

        for (i=4;i+2<=tp;i+=4)

            {a.push_back(pos[i]);b.push_back(pos[i+2]);}

        query();

        ans[1]=1;

        if (tp>1) ans[2]=2;

        rep(i,3,tp)

        {

            if (same[mp(pos[i],pos[i-2])]) ans[i]=ans[i-2];

            else ans[i]=6-ans[i-1]-ans[i-2];

        }

        rep(i,1,3) col[i].clear();

        int now=1;

        rep(i,1,tp)

            while ((now!=pos[i+1]) && (now<=n))

                {col[ans[i]].push_back(now);now++;}

        answer();

    }

    return 0;

}

codeforces选做的更多相关文章

  1. Atcoder 水题选做

    为什么是水题选做呢?因为我只会水题啊 ( 为什么是$Atcoder$呢?因为暑假学长来讲课的时候讲了三件事:不要用洛谷,不要用dev-c++,不要用单步调试.$bzoj$太难了,$Topcoder$整 ...

  2. &lbrack;SDOI2016&rsqb;部分题选做

    听说SDOI蛮简单的,但是SD蛮强的.. 之所以是选做,是因为自己某些知识水平还不到位,而且目前联赛在即,不好花时间去学sa啊之类的.. bzoj4513储能表&bzoj4514数字配对 已写 ...

  3. 20175221 《Java程序设计》迭代和JDB（课下作业，选做）：

    20175221 <Java程序设计> 迭代和JDB(课下作业,选做): 任务详情 1 使用C(n,m)=C(n-1,m-1)+C(n-1,m)公式进行递归编程实现求组合数C(m,n)的功 ...

  4. MyOD&lpar;课下作业，选做&rpar;

    MyOD(课下作业,选做) 代码要求 编写MyCP.java 实现类似Linux下cp XXX1 XXX2的功能,要求MyCP支持两个参数: java MyCP -tx XXX1.txt XXX2.b ...

  5. 迭代和JDB（课下作业，选做）

    迭代和JDB(课下作业,选做) 题目要求 1 使用C(n,m)=C(n-1,m-1)+C(n-1,m)公式进行递归编程实现求组合数C(m,n)的功能 2 m,n 要通过命令行传入 3 提交测试运行截图 ...

  6. 20175312 2018-2019-2 《Java程序设计》第6周课下选做——类定义

    20175312 2018-2019-2 <Java程序设计>第6周课下选做--类定义 设计思路 1.我觉得Book其实就是一个中转的作用,由测试类Bookself通过Book输入数据,然 ...

  7. 20175314薛勐 MyOD&lpar;课下作业，选做&rpar;

    MyOD(课下作业,选做) 要求 编写MyOD.java 用java MyOD XXX实现Linux下od -tx -tc XXX的功能 思路 伪代码: 读取命令行输入的参数(文件名) 以16为每个字 ...

  8. 20155228 2017-11-19 实现mypwd&lpar;选做，加分&rpar;

    20155228 2017-11-19 实现mypwd(选做,加分) 题目和要求 学习pwd命令 研究pwd实现需要的系统调用(man -k; grep),写出伪代码 实现mypwd 测试mypwd ...

  9. 2017-2018-2 20165312 课下选做 MySort

    2017-2018-2 20165312 课下选做 MySort 题目描述 模拟实现Linux下Sort -t : -k 2的功能,参考 Sort的实现. import java.util.*; pu ...

随机推荐

  1. Android学习笔记之使用百度地图实现地图控制

    PS:吾之荣耀,离别已久. 学习内容: 1.实现地图控制. 2.百度地图开发的一些细节     1.实现地图控制:   这一篇主要写在百度地图上添加一些其他控制.上一篇书写了覆盖物的添加,地理编码和反 ...

  2. 通用简单的 分页 SQL

    select                ID,TITLE,CONTENT,USERNAME,REALNAME,UNIT,UNITID,NOWTIMES,ACCEPTERID,ACCEPTERNAM ...

  3. C&num;基础之方法参数

    params params 关键字可以指定在参数数目可变处采用参数的方法参数. 在方法声明中的 params 关键字之后不允许任何其他参数,并且在方法声明中只允许一个 params 关键字 publi ...

  4. 分布式搜索之搭建Solrcloud&lpar;Solr集群&rpar;

    Solrcloud介绍: SolrCloud(solr集群)是Solr提供的分布式搜索方案. 当你需要大规模,容错,分布式索引和检索能力时使用SolrCloud. 当索引量很大,搜索请求并发很高时,同 ...

  5. 前端 SPA 单页应用数据统计解决方案 &lpar;ReactJS &sol; VueJS&rpar;

    前端 SPA 单页应用数据统计解决方案 (ReactJS / VueJS) 一.百度统计的代码: UV PV 统计方式可能存在问题 在 SPA 的前端项目中 数据统计,往往就是一个比较麻烦的事情,Re ...

  6. Linux记录-配置无密码登录

    1.互信的机器都执行 ssh-keygen -t rsa cat ~/.ssh/id_rsa.pub >> /home/hdfs/.ssh/authorized_keys chmod 60 ...

  7. Charles设置HTTPS抓包

    1. 配置 Charles 根证书 点击 Help -> SSL Proxying -> Install Charles Root Certificate 之后会弹出钥匙串,如果不弹出,请 ...

  8. python---windows下安装和使用memcache

    windows版本下memcache地址http://www.runoob.com/memcached/window-install-memcached.html 注意当选择版本>=1.45时需 ...

  9. 2n皇后问题【dfs】

    <题目链接> 题目描述 给定一个n*n的棋盘,棋盘中有一些位置不能放皇后.现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行.同一列或同一条对角线上,任意的两个白皇后 ...

  10. ROS知识（10）----smach&lowbar;viewer的Graph view不能显示状态图

    1.问题 在运行ROS by Example 2--Indigo版本中,运行 smach_viewer,再运行巡逻,命令如下: $ rosrun smach_viewer smach_viewer.p ...

相关文章