Day 2
rank 11 100+35+30=165
本题是一道数论题，求ax+by=c的正整数对(x,y) x>=0并且y>=0
先说下gcd： 求a,b公约数gcd(a,b)
如gcd（4，6）= 2
辗转相除法 gcd(a,b)=gcd(b,a%b)
证明一下，令a=kb+r,那么r=a%b;
设d为(a,b)的一个任意公约数d,所以d|a且d|b
因为r=a-kb因为d|a且d|b，所以d|r注意到我们的d是任意选取的，
那么最大公约数是属于这个公因数集合里的所以gcd(a,b)=gcd(b,a%b)
再说下ex_gcd（a,b,&x,&y）求ax+by=gcd（a,b）的一个整数解 x,y
算法如下：
b=0时gcd(a,b)=gcd(a,0)=a;所以ax=a，所以x=1，y=任意数（这里赋值为0）
ax1+by1=gcd(a,b)=gcd(b,a%b)=bx2+(a%b)y2
引理： a-[a/b]*b=a%b
令a=br+k，左边=br+k-[（br+k）/b]*b=br+k-br=k=a%b=右边
由引理得：ax1+by1=bx2+（a-[a/b]*b）y2=ay2+b（x2-[a/b*b]y2）
由恒等式定理得： x1=y2，y1=x2-[a/b*b]y2
所以求解（x1,y1）只要求出(x2,y2)就可以了
ex_gcd程序如下：
ll ex_gcd(ll a,ll b,ll &x,ll &y)
{
if (b==) { x=;y=; return a;}
ll r=ex_gcd(b,a%b,x,y);
ll t=x;x=y;y=t-a/b*y;
return r;
}
但是这只是求出一组解但我们要求多组解甚至解的个数
令一组解(x0,y0)是初始解 (x1,y1)是要求的解
ax0+by0=gcd(a,b)=ax1+by1
a(x0-x1)=b(y1-y0)两边同时除以gcd(a,b)
设gcd(a,b)=g;a'=a/g;b'b/g
那么就可以写成 a'(x0-x1)=b'(y1-y0) 因为g为a，b最大公约数
那么 a'和b'互质
那么b'|(x0-x1);a'|(y1-y0)设x0-x1=kb'那么y1-y0=ka'
所以x1=x0-kb';y1=y0+ka' k为整数
由此可见方程ax+by=gcd(a,b)如果有解那么一定有无线组解
(x0,y0)==>(x0-kb',y0+ka')
对于一般2元1次不等式ax+by=c若c%gcd(a,b)!=0那么一定无解否则一定有多组解
回到题目让我们求出ax+by=c，通过上面那句话就可以轻易判断有无解，现在考虑解的个数
先把x0 y0调整到正数
x最小时且大于0,y最大，x0-kb'>=0不停的增加k最多可以是kmax= x0/b';xmin=x0-(x0/b')*b'=x0%b'
x最大时y最小且大于0，y0+ka'>=0不停的减去k最多可以是kmin=-y0/a'同理ymin=y0%a'
通过ymin可以求出xmax（带入即可）
求出xmin和xmax后再xmin和xmax之间每隔b‘就有一组解所以就是一个等差数列，个数是(尾项-首相）/公差+1=(xmax-xmin)/b'+1
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ex_gcd(ll a,ll b,ll &x,ll &y)
{
if (b==) { x=;y=; return a;}
ll r=ex_gcd(b,a%b,x,y);
ll t=x;x=y;y=t-a/b*y;
return r;
}
inline ll read()
{
ll X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
int main()
{
freopen("cake.in","r",stdin);
freopen("cake.out","w",stdout);
int T; scanf("%d",&T);
while (T--) {
ll a=read(),b=read(),x,y,c=read();
ll g=ex_gcd(a,b,x,y);
if (c%g!=) {
printf("0\n");
continue;
}
ll g1=a/g,g2=b/g;ll k=c/g;
x=x*(k%g2); y=y*(k%g1); //后面反正要%g1的现在先%防止爆炸
ll xmin=(x%g2+g2)%g2,ymin=(y%g1+g1)%g1;
ll xmax=(c-b*ymin)/a; //通过ymin求xmax
if (xmax-xmin<) {
printf("0\n"); continue;
}
ll ans=((xmax-xmin)/g2)+;//等差数列个数
printf("%lld\n",ans);
}
return ;
}
30pts:
# include <bits/stdc++.h>
using namespace std;
char s[];
bool fun(int z,int a,int c,int k,int m,int n)
{
for (int i=;i<=n;i++) {
z=((a*z+c)/k)%m;
if ((z<m/)&&(s[i]!='')) return false;
else if ((z>=m/)&&(s[i]!=''))return false;
}
return true;
}
int main()
{
freopen("zero.in","r",stdin);
freopen("zero.out","w",stdout);
int a,c,k,m,n;
scanf("%d%d%d%d%d",&a,&c,&k,&m,&n);
scanf("%s",s+);
int ans=;
for(int z=;z<=m;z++) {
if (fun(z,a,c,k,m,n)) ans++;
}
printf("%d\n",ans);
return ;
}
100pts:倍增+hash
题解原文：
倍增HASH，用倍增记录每个值跳2^i次后会到哪个值，构成的串的HASH值，
然后根据n的二进制直接算答案就行了，倍增的时候要滚存。
#include <bits/stdc++.h> using namespace std; const int mo1 = ;
const int mo2 = ;
const int base1 = ;
const int base2 = ;
const int M = ;
const int N = ; vector<int>a[M];
pair<int, int>HASH;
int to[M][], Pow1[N], Pow2[N], now[M];
pair<int, int>Hash[M][], nowhash[M];
int ans;
char s[N]; inline void Ch(pair<int, int> &now, int C)
{
now.first = 1ll * now.first * Pow1[C] % mo1;
} inline void Add(pair<int, int> &now, pair<int, int> A)
{
now.first = now.first + A.first;
if(now.first >= mo1)now.first -= mo1;
} inline int check(pair<int, int> a, pair<int, int> b)
{
return ((a.first == b.first) && (a.second == b.second));
} int main()
{
freopen("zero.in", "r", stdin);
freopen("zero.out", "w", stdout);
int A, c, k, m, n;
Pow1[] = Pow2[] = ;
scanf("%d%d%d%d%d", &A, &c, &k, &m ,&n);
for(int i = ;i <= n;i++)
{
Pow1[i] = 1ll * Pow1[i - ] * base1 % mo1;
}
int M = m >> ;
for(int i = ;i < m;i++)
{
int z = i;
now[i] = i;
z = ((1ll * A * z + c) / k) % m;
to[i][] = z;
Hash[i][].first = (z >= M) + ;
}
scanf("%s", s);
if(n & )
{
for(int i = ;i < m;i++)
{
nowhash[i] = Hash[now[i]][];
now[i] = to[now[i]][];
}
}
for(int i = ;i < n;i++)
{
HASH.first = (1ll * HASH.first * base1 + s[i] - '' + ) % mo1;
} for(int x = ;x <= ;x++)
{
for(int i = ;i < m;i++)
{
to[i][x & ] = to[to[i][(x - ) & ]][(x - ) & ];
Hash[i][x & ] = Hash[i][(x - ) & ];
Ch(Hash[i][x & ], << (x - ));
Add(Hash[i][x & ], Hash[to[i][(x - ) & ]][(x - ) & ]);
}
if(n & ( << x))
{
for(int i = ;i < m;i++)
{
Ch(nowhash[i], << x);
Add(nowhash[i], Hash[now[i]][x & ]);
now[i] = to[now[i]][x & ];
}
}
}
for(int i = ;i < m;i++)
if(check(nowhash[i], HASH))ans++;
printf("%d\n", ans);
}
题意：
给一个DAG，选择尽量多的点使彼此之间不存在祖先-后代关系。
5%：
暴力枚举每一个点是否被选中，时间复杂度:O(2^n)
20%：
在上一个做法的基础上加上一些剪枝。时间复杂度：O(2^n)。
此算法亦可通过n==200的测试点，且只需要16ms（luogu上）。
树的部分分：
容易发现选择全部叶节点即可。时间复杂度：O(n)
“每个会员要么没有上司，要么没有下属”的：
容易发现此时的DAG是一个二分图。使用经典的二分图最大独立集算法（点数-最大匹配数）即可。时间复杂度：O(m*sqrt(n))。
“全是直接下属”的：
我也不知道怎么做，这个部分分只是为了让***的错误算法多拿一些分。
100%：
容易发现此题是一道DAG最大独立集裸题（参见 CTSC2008祭祀），而且不用输出方案。（但我真的不是出的原题，纯属巧合）
由于时间原因，在此复制@白苏小公子喵 的题解：
在有向无环图中，我们定义：
链：图上一些点的集合，对于链上任意两个点x、y，满足x能到达y或者y能到达x。
反链：图上一些点的的集合，对于反链上任意两个点x、y，满足x不能到达y并且y不能到达x。
所以就是很显然的求最长反链长度了~
有以下Dilworth定理：
最长反链长度=最小链覆盖（选取最少的链覆盖所有的点）->证明详见最长反链与最小链覆盖
以及其对偶定理：最长链长度=最小反链覆盖
所以就又转化成了求最小路径（链）覆盖了，来看怎么求：
选择建一个二分图，两边各有n个点，原来的点node分别对应两个图中的node1、node2。如果原图中存在边 x->y，那么就在二分图上建立边 x1->y2。
跑一遍匈牙利，则有 原图最小路径覆盖=原点数n-二分图最大匹配
（当然也可以用网络流，则有 原图最小路径覆盖=原点数n-最大流）
为什么呢？考虑每在二分图上连一条边，就相当于将两条路径连成一条，那么最小链覆盖数就减少了1（少用一条链覆盖所有点了）。我们将一个点拆成两个，跑二分图最大匹配，避免了路径相交的问题，保证所选出来的每一条一定为一条链。
#include<bits/stdc++.h>
#define maxn 10010
#define int64 long long
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
bitset<maxn> isfa[maxn];
int n,m,que[maxn],cnt;
int ind[maxn],top[maxn];
vector<int> v[maxn],vb[maxn];
struct edge{
int u,v,cap;
};
struct Dinic{
int n,s,t,dis[maxn],cur[maxn],que[maxn];
vector<edge>e;vector<int>v[maxn];
void Init(int n){
this->n=n;e.clear();
for(int i=;i<n;i++)v[i].clear();
}
void AddEdge(int x,int y,int flw){
e.push_back((edge){x,y,flw});
e.push_back((edge){y,x,});
v[x].push_back(e.size()-);
v[y].push_back(e.size()-);
}
int bfs(){
memset(dis,0x3f,sizeof dis);
int l=,r=;que[]=s;dis[s]=;
while(l<=r){
int p=que[l++],to,i;
for(int t=;t<(int)v[p].size();++t)if(e[i=v[p][t]].cap && dis[to=e[i].v]>1e9)
dis[to]=dis[p]+,que[++r]=to;
}
return dis[t]<1e9;
}
int dfs(int p,int a){
if(p==t || !a)return a;
int sf=,flw;
for(int &i=cur[p],to;i<(int)v[p].size();++i){
edge &E=e[v[p][i]];
if(dis[to=E.v]==dis[p]+ && (flw=dfs(to,min(a,E.cap)))){
E.cap-=flw;e[v[p][i]^].cap+=flw;
a-=flw;sf+=flw;
if(!a)break;
}
}
return sf;
}
int dinic(int s,int t){
this->s=s;this->t=t;
int flw=;
while(bfs()){
memset(cur,,sizeof cur);
flw+=dfs(s,1e9);
}
return flw;
}
}sol;
int main(){
FO(dance);
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
v[x].push_back(y);ind[y]++;
vb[y].push_back(x);
}
int l=,r=;
for(int i=;i<=n;i++)if(!ind[i])que[++r]=i;
while(l<=r){
int now=que[l++];top[++cnt]=now;
for(int i=;i<(int)v[now].size();i++)
if(!--ind[v[now][i]])que[++r]=v[now][i];
}
for(int i=;i<=n;i++){
int p=top[i];isfa[p][p]=;
sol.AddEdge(,i*,);
sol.AddEdge(i*+,,);
for(int j=;j<(int)vb[p].size();j++)
isfa[p]|=isfa[vb[p][j]];
for(int j=;j<=n;j++)if(isfa[p][j] && p!=j)
sol.AddEdge(j*,p*+,);
}
printf("%d\n",n-sol.dinic(,));
return ;
}