Contest Link Official Editorial
Given are integers \(S\) and \(P\) . Is there a pair of positive integers \((N,M)\) such that \(N+M=S\) and \(N×M=P\) ?
签到题。 \(1e9\) 不能直接枚举，那么就枚举 \(P\) 较小的约数即可。
//Author: RingweEH
S=read(); P=read(); ll lim=sqrt(P);
for ( ll i=1; i<=lim; i++ )
{
if ( P%i ) continue;
ll j=P/i;
if ( (i+j)==S ) { printf( "Yes\n" ); return 0; }
}
printf( "No\n" );
Given is a string \(S\) of length \(N\) consisting of lowercase English letters. Snuke can do this operation any number of times: remove fox occurring as a substring from \(s\) and concatenate the remaining parts of \(s\) .
What is the minimum possible length of \(s\) after some number of operations by Snuke?
我是乱搞过的……不知道 WA+TLE 了多少发。具体就是由于新出现的 fox 只能在删掉的地方，所以考虑每次删掉一个就把两边的搞一遍。然后再加了个暴力捡漏？？
正解：令 \(t\) 初始为一个空串，然后重复下面的步骤直到 \(s\) 为空串：
fox 那么删除掉并计入答案。妙啊。
//Author: RingweEH
int check( int pos )
{
if ( s[pos]==‘f‘ ) return 1;
if ( s[pos]==‘o‘ ) return 2;
if ( s[pos]==‘x‘ ) return 3;
return 0;
}
int repos( int l,int r )
{
while ( 1 )
{
if ( l<0 || r>=n ) return r;
if ( vis[l] || vis[r] ) return r;
int cl=check(l),cr=check(r);
if ( !cl || !cr ) return r;
if ( (cl!=2) && (cr!=2) ) return r;
if ( (cl==2) && (cr==2) ) return r;
if ( cl==2 )
{
if ( (l==0) || vis[l-1] ) return r;
l--; cl=check(l);
if ( cl!=1 ) return r;
if ( cr!=3 ) return r;
cnt++; vis[l]=1; vis[l+1]=1; vis[r]=1; l--; r++;
}
if ( cr==2 )
{
if ( (r>=(n-1)) || vis[r+1] ) return r;
r++; cr=check(r);
if ( cr!=3 ) return r-1;
if ( cl!=1 ) return r-1;
cnt++; vis[l]=1; vis[r-1]=1; vis[r]=1; l--; r++;
}
}
}
int main()
{
n=read(); cin>>s; //scanf( "%s",s );
memset( vis,0,sizeof(vis) );
for ( int i=0; i<n-2; i++ )
{
if ( vis[i] ) continue;
if ( (s[i]==‘f‘) && (s[i+1]==‘o‘) && (s[i+2]==‘x‘) )
{
cnt++; vis[i]=1; vis[i+1]=1; vis[i+2]=1; i=repos( i-1,i+3 )-1;
}
}
string s2="";
for ( int i=0; i<n; i++ )
if ( !vis[i] ) s2=s2+s[i];
while( s2.find("fox")!=-1 )
{
s2.erase( s2.find("fox"),3 ); n -= 3;
}
printf( "%d",n-cnt*3 );
}
Given is an undirected connected graph with \(N\) vertices numbered 11 to \(N\), and \(M\) edges numbered \(1\) to \(M\) . The given graph may contain multi-edges but not self loops.
Each edge has an integer label between \(1\) and \(N\) (inclusive). Edge \(i\) has a label \(c_i\) , and it connects Vertex \(u_i\) and \(v_i\) bidirectionally.
Snuke will write an integer between \(1\) and \(N\) (inclusive) on each vertex (multiple vertices may have the same integer written on them) and then keep only the edges satisfying the condition below, removing the other edges.
Condition: Let \(x\) and \(y\) be the integers written on the vertices that are the endpoints of the edge. Exactly one of \(x\) and \(y\) equals the label of the edge.
We call a way of writing integers on the vertices good if (and only if) the graph is still connected after removing the edges not satisfying the condition above. Determine whether a good way of writing integers exists, and present one such way if it exists.
先在图上求一棵生成树，然后构造。如果不存在生成树就无解。
设点 \(1\) 为根，任意涂色，然后向下 \(\text{dfs}\) 。对于一条边 \((u,v,w)\) ，如果 \(tag[x]==w\) 那么给 \(v\) 任意涂色，否则 \(tag[v]=w\) ，这样即可构造出合法解。
为什么把 add( read(),read(),read() ) 改成 u=read(),v=read(),w=read(),add( u,v,w ); 就 Accepted 了啊……没明白诶。
哦，它是函数啊，那没事了。
//Author: RingweEH
void dfs( int u )
{
for ( int i=head[u]; i; i=e[i].nxt )
{
int v=e[i].to;
if ( !tag[v] )
{
if ( tag[u]==e[i].val ) tag[v]= ( tag[u]==1 ) ? 2 : 1;
else tag[v]=e[i].val;
dfs( v );
}
}
}
Given are an integer \(N\) and four characters \(cAA\) , \(cAB\) , \(cBA\) and \(cBB\) . Here, it is guaranteed that each of those four characters is A or B.
Snuke has a string \(s\) , which is initially AB.
Let \(|s|\) denote the length of \(s\). Snuke can do the four kinds of operations below zero or more times in any order:
A, \(s_{i+1}\) = A and insert \(cAA\) between the \(i\)-th and \((i+1)\)-th characters of \(s\) .A, \(s_{i+1}\) = B and insert \(cAB\) between the \(i\)-th and \((i+1)\)-th characters of \(s\).B, \(s_{i+1}\) = A and insert \(cBA\) between the \(i\)-th and \((i+1)\)-th characters of \(s\).B, \(s_{i+1}\) = B and insert \(cBB\) between the \(i\)-th and \((i+1)\)-th characters of \(s\).Find the number, modulo \((10^9+7)\) , of strings that can be \(s\) when Snuke has done the operations so that the length of \(s\) becomes \(N\) .
发现只有 4 种变化，一共16种情况。可以大力分讨一下。
//Author: RingweEH
void power()
{
int b=n-3,res=1;
for ( int i=1; i<=b; i++ )
res=res*2%mod;
printf( "%d\n",res );
}
void fib()
{
int b=n-3,a1=1,a2=1;
for ( int i=1; i<=b; i++ )
{
int tmp=(a1+a2)%mod;
a1=a2; a2=tmp;
}
printf( "%d\n",a2 );
}
There are \(N\) isu - chairs in Japanese - arranged from left to right. The \(i\)-th chair from the left has the ID number \(a_i\) . Here, it is guaranteed that \(a_i\) are distinct.
Snuke has decided to mark some of the chairs and throw away the rest. Initially, no chair is marked. We call a choice of marked chairs good when the IDs of the marked chairs are monotonically increasing from left to right.
Snuke has decided to do the following procedure to mark chairs:
It can be proved that the expected value of the number of chairs that remain at the end of the procedure is a rational number. Let this value be \(P/Q\) , an irreducible fraction. Additionally, let \(M=10^9+7\) . Then, we can prove that there uniquely exists an integer \(R\) between \(0\) and \(M?1\) (inclusive) such that \(P≡Q×R(modM)\) , and that value equals \(P×Q?1(modM)\) , where \(Q?1\) is the modular multiplicative inverse of \(Q\). Find \(R\) .
Given is a tree with \(N\) vertices numbered \(1\) to \(N\), and \(N?1\) edges numbered \(1\) to \(N?1\) . Edge \(i\) connects Vertex \(a_i\) and \(b_i\) bidirectionally and has a length of \(1\) .
Snuke will paint each vertex white or black. The niceness of a way of painting the graph is \(max(X,Y)\) , where \(X\) is the maximum among the distances between white vertices, and \(Y\) is the maximum among the distances between black vertices. Here, if there is no vertex of one color, we consider the maximum among the distances between vertices of that color to be \(0\) .
There are \(2^N\) ways of painting the graph. Compute the sum of the nicenesses of all those ways, modulo \((10^9+7)\) .
所以题意就是求所有染色方案下白色直径和黑色直径中较大值的和。
考虑一条直径，设两端为 \(u_1,u_2\) ，并钦定 \(u_1=black\) .
如果两点颜色相同则贡献为 \(dis[u_1][u_2]\times 2^{N-2}\) 。
如果不同，易知答案一定是 \(u_1,v\) 或者 \(u_2,v\) 之间的距离。（ \(v\) 为任意点）
记 \(dis[i][0]\) 为 \(i\) 到 \(u_1\) 的距离，\(dis[i][1]\) 为 \(i\) 到 \(u_2\) 的距离。最终答案就是 \(\sum\max(dis[i][0],dis[i][1])\)
考虑枚举这个最大值，尝试求出 “存在多少方案所选的最大值不大于这个数”，记为 \(f[i]\) .
那么有
如果存在某一对 \(dis[i][0],dis[i][1]\) 均大于 \(i\) ，那么 \(f[i]=0\) . 处理了这种特殊情况后，再令 \(g[i]=\max(dis[i][0],dis[i][1])\) ，有
直接对 \(g\) 排序，然后扫一遍即可得到 \(f[i]\) .
最终答案等于
其中 \(D\) 为直径长度。
//Author: RingweEH
void dfs( ll u,ll fa )
{
dep[u]=dep[fa]+1;
for ( ll v : gg[u] )
if ( v!=fa ) dfs( v,u );
}
int main()
{
n=read();
for ( ll i=1,u,v; i<n; i++ )
u=read(),v=read(),gg[u].push_back(v),gg[v].push_back(u);
//---------------------beginning-------------------------
dep[0]=-1; dfs( 1,0 );
ll u1=-1,mx=0;
for ( ll i=1; i<=n; i++ )
if ( dep[i]>mx ) mx=dep[i],u1=i;
dfs( u1,0 );
for ( ll i=1; i<=n; i++ )
dis1[i]=dep[i];
ll u2=-1; mx=0;
for ( ll i=1; i<=n; i++ )
if ( dep[i]>mx ) mx=dep[i],u2=i;
dfs( u2,0 );
for ( ll i=1; i<=n; i++ )
dis2[i]=dep[i];
//------------------------diameter---------------------------
ll gcnt=0;
for ( ll i=1; i<=n; i++ )
if ( i!=u1 && i!=u2 ) g[++gcnt]=max( dis1[i],dis2[i] );
sort( g+1,g+1+gcnt ); ll lim=0;
for ( ll i=1; i<=n; i++ )
lim=max( lim,min(dis1[i],dis2[i]) );
//-----------------------get_g---------------------------------
for ( ll i=mx; i>=lim; i-- )
{
while ( gcnt>=1 && g[gcnt]>i ) gcnt--;
f[i]=power(2,gcnt);
}
//----------------------get_f----------------------------------
ll tmp=0,ans=0;
for ( ll i=lim; i<=mx; i++ )
{
f[i]=((f[i]-tmp)%mod+mod)%mod;
tmp=(tmp+f[i])%mod;
ans=(ans+f[i]*i)%mod;
}
ans=(ans+mx*power(2,n-2) )%mod;
//--------------------get_ans-----------------------------
printf( "%lld",ans*2%mod );
}
原文：https://www.cnblogs.com/UntitledCpp/p/14027475.html