P6661 Pomniejszenie
还算正常的贪心
P6661
修改\(A\)与\(B\)高位尽可能多的数字相同，从第\(p\)位开始不同，第\(p\)位满足\(a[i]<b[i]\)，把从\(p+1\)位到最后一位的数尽可能多的改成\(9\)。
现在考虑位置\(p\)的选择：
- \(p\)满足的条件：1. 从\(1\)到\(p\)中\(a[i]\)与\(b[i]\)不同（需要修改）的数量\((k_1)\)不超过\(k\)。2. 从\(p+1\)到\(n\)（可能被修改）的数量不小于还需要修改的次数。
- 在\(b[i]=0\)时\(a[i]\)做不到小于\(b[i]\)，所以\(i\)不可以作为\(p\)。
- \(b[i]>a[i]\)时，\(a[i]\)可以不修改，所以只需要满足\(k_1<=k\)并且\(n-i>=k-k_1\)。
- 在\(a[i]=0\)并且\(b[i]=1\)时不可修改，剩下的情况可以做修改，所以要满足\(k_1+1<=k\)并且\(n-i>=k-k_1-1\)。
在\(i<p\)时，答案为\(b[i]\)。
在\(i=p\)时，如果这一位为了确保达到修改次数必须修改并且\(b[p]-1=a[p]\)，答案为\(b[p]-2\)，其余情况答案为\(b[p]-1\)。
在\(i>p\)时，如果\(a[i]=9\)并且\(a[i]\)必须修改时答案为\(8\)，其余情况在还有修改机会剩余时答案为\(9\)。
在无修改机会剩余时答案为\(a[i]\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int t,k;
char a[100010],b[100010];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%s%s%d",a+1,b+1,&k);
int n=strlen(a+1);
int p=0,k1=0;
for(int i=1;i<=n;i++)
{
if(b[i]!='0')
{
if(a[i]<b[i]&&k1<=k&&n-i>=k-k1)p=i;
if((a[i]>'0'||b[i]>'1')&&k1+1<=k&&n-i>=k-k1-1) p=i;
}
if(a[i]!=b[i])k1++;
}
if(!p) {printf("-1\n");continue;}
int ans=0;
for(int i=1;i<=n;i++)
{
if(i<p) ans=b[i]-'0';
else if(!k) ans=a[i]-'0';
else if(i==p) ans=b[i]-'0'-1-(a[i]+1==b[i]&&n-i+1==k);
else ans=9-(a[i]=='9'&&n-i+1==k);
k-=ans!=a[i]-'0';
cout<<ans;
}
printf("\n");
}
}
P6659 Najmniejsza wspólna wielokrotność
不太正常的二分
P6659
在区间长度大于\(3\)时对于极限的\(n\)为\(10^{18}\)答案内的数只会在\(10^{6}\)以内，可以暴力枚举左右端点存在\(map\)里。
区间长度为\(1\)的区间中只有\(x\)和\(x+1\)而且\(lcm(x,x+1)=x\times (x+1)\)，可以二分找到答案。
区间长度为\(2\)的区间中\(x,x+1,x+2\)的最小公倍数在\(x\)为奇数时是三个数的乘积，在\(x\)为偶数时是三个数乘积的一半，同样可以二分找到区间端点。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const ll maxm=1e18+5;
ll z,n;
struct node
{
ll l,r;
};
map<ll,node> m;
ll solve1()
{
ll l=1,r=1e9;
while(l<r)
{
ll mid=(l+r+1)>>1;
if(mid*(mid+1)>n) r=mid-1;
else l=mid;
}
if(l*(l+1)==n)
{
printf("%lld %lld\n",l,l+1);
return 1;
}
return 0;
}
ll solve2(int o)
{
ll l=1,r=2e6;
while(l<r)
{
ll mid=(l+r+1)>>1;
if(mid*(mid+1)*(mid+2)>n) r=mid-1;
else l=mid;
}
if (((int)l&1)!=o) return 0;
if(l*(l+1)*(l+2)==n)
{
printf("%lld %lld\n",l,l+2);
return 1;
}
return 0;
}
signed main()
{
for(ll i=1;i<=1000010;i++)
{
ll w=i*(i+1);
for(ll j=i+2;j<=100010;j++)
{
ll g=__gcd(j,w);
w=w/g;
if(w>maxm/j)break;
w=w*j;
if(m.find(w)==m.end())
{
m[w].l=i; m[w].r=j;
}
}
}
scanf("%lld",&z);
while(z--)
{
scanf("%lld",&n);
if(m.find(n)!=m.end())
{
printf("%lld %lld\n",m[n].l,m[n].r);
continue;
}
if (solve1()) continue;
if (solve2(1)) continue;n*=2;
if (solve2(0)) continue;
cout<<"NIE"<<endl;
}
}
P6663 Układ scalony
大诡异的构造
P6663
题意概括
在\(n\times m\)的网格图中每个格子为一个点，只向相邻的格子连边权为\(1\)的边，使其直径恰好为\(k\)。
题解
把\(n\times m\)个点连接成树，直径最长的情况是把所有点串成一条链，此时直径为\(n\times m-1\)。直径最短的情况是把距离最远的点（如左下角和右上角）连起来，此时直径为\((n-1)+(m-1)\)，对于\(n\)和\(m\)都是偶数的情况，其他点与找到的直径相连时会使直径增长\(1\)。
有图有真相：
最短直径的寻找方式：尽可能串连一排把图平均分成两个部分，再在两端分别向左右延申到网格边缘。
右图\(m\)为奇数，最短直径（可以）是蓝色线条，长度为\(n+m-2\)。
左图\(m\)和\(n\)都是偶数，浅蓝色线条和部分深蓝色线条直接连接左下角和右上角的点，长度没有连接左上角和左下角的深蓝色线条长，由于深蓝色竖线尽可能居中安置，真实直径（深蓝色）会比\(n+m-2\)（浅蓝色加部分深蓝色）多一。
构造方式：
先把左上角和右下角的点按照（形似）上述构造最短直径（对于\(n\)和\(m\)都是偶数的情况是长度少一的部分直径）的方式连接，剩下的直接（暂时）像鱼刺一样连接在所画的链上（保证尽量不影响直径长度），如果现在连接出来的链长度小于\(k\)，使一头从外向内卷曲（从外围缩减鱼刺的长度，把断掉的部分接到链上），链的长度到达\(k\)后，剩余的鱼刺按照鱼刺样式相连。
诡异的图解：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
const int maxn=1e3+10;
int vis[maxn][maxn];
int f;
void add(int a,int b,int a1,int b1)
{
if(f) swap(a,b),swap(a1,b1);
printf("%d %d %d %d\n",a,b,a1,b1);
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
if(k>=n*m||k<n+m-1-((n&1)||(m&1))) {printf("NIE"); return 0;}
printf("TAK\n");
if(m&1) swap(n,m),f=1;
int mid=n/2+1;
k-=n+m-2;
int a=min(k,(mid-1)*(m-1)),b=k-a;
if(n%2==0&&k<m-1) a--;
int x=1,y=1;
while(a--)
{
int x1=x,y11=(x&1)?y+1:y-1;
if(y11==m+1) y11=m,x1++;
if(y11==1) y11=2,x1++;
add(x,y,x1,y11);
x=x1; y=y11;
vis[x][y]=1;
}
x=n; y=m;
while(b--)
{
int x1=x,y11=((n-x)&1)?y+1:y-1;
if(y11==m) y11=m-1,x1--;
if(y11==0) y11=1,x1--;
add(x,y,x1,y11);
x=x1; y=y11;
vis[x][y]=1;
}
for(int i=1;i<m;i++)
{
add(mid,i,mid,i+1);
}
for(int i=1;i<n;i++)
{
for(int j=1;j<=m;j++)
{
if(!vis[i][j]&&!vis[i+1][j]) add(i,j,i+1,j);
}
}
}
P6662 Przedszkole
缝合怪警告
P6662
题意概括：
在有\(n\)个点\(m\)条无向边的途中，给每个节点染色，至多使用\(k\)种颜色，要求一条边所连接的两个节点颜色不能相同。（多组询问\(n,m\)和连边方式不变，\(k\)不同）
缝合部分（残肢）：
- \(n\leq 15\)
- \(m\leq 24\)
- 图只由环组成。
题解
1.
对于第一部分，由于\(n\)比较小，可以用状态压缩枚举每一个点的状态。设\(f_{i,s}\)为已经使用了\(i\)种颜色，节点状态为\(s\)（\(0\)表示未涂色，\(1\)表示已涂色）的方案数。转移时枚举\(s\)的子集\(t\)，把\(t\)中为\(1\)的点涂成相同的颜色，预处理每个点不能和哪些点连边，先枚举每一种状态并排除不合法的状态，再用合法（\(k\)内部的点不互相连边，\(t\)不为空集）的\(t\)转移，转移方程为：\(f_{(i,s)}=f_{(i,s)}+f_{(i-1,s-t)}\)。最后求出答案（用从\(1\)到\(k\)种颜色，给每一个点都染色的方案数累加）：\(ans=\sum\limits_{i=1}^{n}\times C_{k}^{i}\times f_{(i,2^n-1)}\)。时间复杂度为：\(O(n3^m+Tn^2)\)
2.
对于第二部分，由于\(m\)比较小考虑\(O(n^2)\)枚举，可以枚举每一条边所连的点的状态，在用总数减去不合法的方案数。
现在考虑不合法的方案数的求解。设\(A_i\)表示至少有\(i\)个点不合法的方案集合，\(c_i\)为正好有\(i\)个点不合法的方案数，\(A_i\)集合的大小\(|A_i|=c_{n-i}\times k^{n-i}\)（正好有\(i\)个点不合法，其余的点任意涂色），根据容斥原理\(|\bigcup\limits_{i=1}^{n}A_i|=\sum\limits_{m=1}^{n}(-1)^{m-1}\sum\limits_{a_i<a_i+1}|\bigcap\limits_{i=1}^{m}A_{a_i}|\)，得到\(|\bigcup\limits_{i=1}^{n}A_i|=\sum\limits_{j=1}^{n}(-1)^{j-1}|A_j|\)，最终答案为\(k^n-|\bigcup\limits_{i=1}^{min(n,m)}A_i|\)
现在稍微化简一下：
预处理出\(c_i\)，遍历每一条边，分为端点颜色相同和颜色不同两种情况向下递归，遍历了偶数条边时加上方案数，遍历了奇数条边时减去方案数，用可撤销并查集维护每个点的颜色，递归时如果一条边的两个点颜色已经相同，直接返回。时间复杂度为$O(n3n+Tn2)。
3.
对于第三部分，图由很多环组成。先单独考虑一个环的方案数，设\(f_i\)为一个长度为\(i\)的环的方案数，转移时如果第\(1\)个点和第\(i-1\)个点颜色相同，第\(i\)个点就有\(k-1\)种方案，薅掉第一个点，剩下的就是一个由\(i-2\)个点组成的环，如果第\(1\)个点和第\(i-1\)个点颜色不同，第\(i\)个点有\(k-2\)种方案，剩下\(i-1\)个点可以直接点扣成环，所以\(f_i=(k-1)\times f_{i-2}+(k-2)\times f_{i-1}\)。
现在为了保证时间复杂度不炸裂，让我们发挥高贵的高中牲必备的数学水平，从二阶递推公式求解通项公式，首先解特征方程\(x^2=(k-2)x+k-1\)解得\(x_1=-1,x_2=k-1\)，把\(f_2=k(k-1)=k^2-k\)，\(f3=k(k-1)(k-2)=k^3-3k^2+2k\)代人\(f_n=c_1\times (k-1)^n+c_2\times (-1)^n\)，解出\(c_1=1\)，\(c_2=k-1\)，所以\(f_n=(k-1)^n+(-1)^n(k-1)\)。
最终答案为所有环的方案数乘积。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int maxn=1e5+10;
int n,m,z;
const ll mod=1e9+7;
ll qpow(ll a,int b)
{
ll tmp=1;while(b){if(b&1) tmp=(tmp*a)%mod; a=a*a%mod; b=b>>1; } return tmp%mod;
}
ll C(int x,int y)
{
if(x<y)return 0;
ll tmp=1;
for(int i=1;i<=y;i++)
{
tmp=tmp*(x-i+1)%mod*qpow(i,mod-2)%mod;
}
return tmp;
}
namespace task1
{
int p[maxn],vis[1<<17],f[17][1<<17];
void main()
{
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%lld%lld",&u,&v); u--; v--;
p[u]|=(1<<v); p[v]|=(1<<u);
}
for(int s=0;s<(1<<n);s++)
{
for(int i=0;i<n;i++)
{
if(((1<<i)&s)&&(p[i]&s)) vis[s]=1;
}
}
f[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int s=0;s<(1<<n);s++)
{
for(int j=s;j!=0;j=(j-1)&s)
{
if(!vis[j]) f[i][s]=(f[i][s]+f[i-1][s-j])%mod;
}
}
}
for(int i=1;i<=z;i++)
{
ll ans=0;
int k;scanf("%lld",&k);
for(int j=1;j<=n;j++)
{
ans=(ans+C(k,j)*f[j][(1<<n)-1]%mod)%mod;
}
printf("%lld\n",ans);
}
}
}
namespace task2
{
struct node
{
int u,v;
};
node e[maxn];
int fa[maxn],c[maxn];
int getfa(int x)
{
return fa[x]==x?x:getfa(fa[x]);
}
void dfs(int x,int cnt,int op)
{
if(x==m+1) {c[cnt]+=op;return;}
int uu=getfa(e[x].u),vv=getfa(e[x].v);
if(uu==vv) return;
else
{
dfs(x+1,cnt,op);
fa[vv]=uu;
dfs(x+1,cnt-1,-op);
fa[vv]=vv;
}
}
void main()
{
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&e[i].u,&e[i].v);
}
for(int i=1;i<=n;i++) fa[i]=i;
dfs(1,n,1);
for(int z1=1;z1<=z;z1++)
{
int k; scanf("%lld",&k);
ll ans=0;
for(int i=0;i<=min(n,m);i++)
{
ans=(ans+c[n-i]*qpow(k,n-i)%mod+mod)%mod;
}
ans=(ans%mod+mod)%mod;
printf("%lld\n",ans);
}
}
}
namespace task3
{
struct node
{
int to,nxt;
};
node t[2*maxn];
int head[maxn],tot=1;
void add(int u,int v)
{
tot++; t[tot].to=v; t[tot].nxt=head[u]; head[u]=tot;
}
int vist[2*maxn],dfn[maxn],dfn1,low[maxn],sz[maxn],scc[maxn],vis[maxn],s[maxn],tp,scc1;
void tarjan(int u)
{
dfn[u]=low[u]=++dfn1; s[++tp]=u; vis[u]=1;
for(int i=head[u];i!=0;i=t[i].nxt)
{
int v=t[i].to;
if(!vist[i])
{
vist[i]=vist[i^1]=1;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(vis[u]) low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u])
{
scc1++;
while(s[tp]!=u)
{
scc[s[tp]]=scc1; sz[scc1]++; vis[s[tp]]=0; tp--;
}
scc[s[tp]]=scc1; sz[scc1]++; vis[s[tp]]=0; tp--;
}
}
ll f(int x1,int k1)
{
return (qpow(k1-1,x1)+((x1&1)?-1:1)*(k1-1))%mod;
}
void main()
{
for(int i=1;i<=m;i++)
{
int u,v; scanf("%lld%lld",&u,&v);
add(u,v); add(v,u);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i]) tarjan(i);
}
for(int i=1;i<=z;i++)
{
int k; scanf("%lld",&k);
ll ans=1;
for(int j=1;j<=scc1;j++)
{
ans=ans*f(sz[j],k)%mod;
}
ans=(ans%mod+mod)%mod;
printf("%lld\n",ans);
}
}
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&z);
if(n<=15)
{
task1::main();
return 0;
}
if(m<=24)
{
task2::main();
return 0;
}
task3::main();
return 0;
}