A.Hashing Trees
題目大意:給定數組a[i],其中a[i]表示深度為i的節點有a[i]個,問是否存在兩個不同構的樹同時滿足這個條件。如果有,請輸出。
簡要題解:有很多種構造方案。我的做法是,第一次把所有深度為i的節點都向深度為i-1的第一個節點連邊。第二次,嘗試分出一個深度為i的節點向深度為i-1的第二個節點連邊。如果可以這樣生成兩棵樹,則有解。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#define maxn 200010
using namespace std;
vector<int> v[maxn];
int a[maxn],f[maxn];
int n,h,cnt;
bool w=;
int main()
{
scanf("%d",&h);
for (int i=;i<=h;i++) scanf("%d",&a[i]);
cnt=;v[].push_back();
for (int i=;i<=h;i++)
{
if (w && a[i]!= && v[i-].size()>)
{
w=;v[i].push_back(++cnt);f[cnt]=v[i-][];
for (int j=;j<a[i];j++) v[i].push_back(++cnt),f[cnt]=v[i-][];
}
else for (int j=;j<=a[i];j++) v[i].push_back(++cnt),f[cnt]=v[i-][];
}
if (w) puts("perfect");
else
{
puts("ambiguous");
printf("0");cnt=;
for (int i=;i<=h;i++)
{
for (int j=;j<=a[i];j++) printf(" %d",cnt);
cnt+=a[i];
}
printf("\n");
printf("0");
for (int i=;i<=h;i++)
{
for (int j=;j<v[i].size();j++) printf(" %d",f[v[i][j]]);
}
printf("\n");
}
return ;
}
B. GCD of Polynomials
題目大意:構造兩個度數不超過n的多項式,使他們求GCD時,調用GCD過程的次數恰好為n。要求每一項的系數為-1或0或1。
簡要題解:注意到,每調用一次GCD過程,多項式的次數都會減一。是以最後的答案多項式一定是n次和n-1次的。考慮用最初的x和1,遞推到n次。我使用的做法是,每次枚舉将高次多項式乘(x+(-1/0/1)),低次多項式乘-1/1,構造出新的高次多項式。最後構造出解。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<bitset>
using namespace std;
int da[]={-,-,,,,};
int db[]={,-,,-,,-};
int n,m;
int a[][],b[][];
int c[];
bool solve(int x)
{
if (x==n) return ;
x++;
for (int k=;k<;k++)
{
a[x][]=da[k]*a[x-][]+db[k]*b[x-][];
for (int i=;i<=x;i++) a[x][i]=a[x-][i-]+da[k]*a[x-][i]+db[k]*b[x-][i];
bool w=;
for (int i=;i<=x;i++) if (a[x][i]>= || a[x][i]<=-) {w=;break;}
if (w)
{
for (int i=;i<x;i++) b[x][i]=a[x-][i];
if (solve(x)) return ;
}
}
return ;
}
int main()
{
scanf("%d",&n);
a[][]=;b[][]=;
if (solve())
{
printf("%d\n",n);
for (int i=;i<=n;i++) printf("%d ",a[n][i]);printf("\n");
printf("%d\n",n-);
for (int i=;i<n;i++) printf("%d ",b[n][i]);printf("\n");
}
else puts("-1");
return ;
}
C.Bipartite Segments
題目大意:給定一個無偶環的無向圖,m次詢問,每次詢問[l,r]中能取出多少個子區間[x,y],滿足隻選擇[x,y]中的點和邊,不會形成奇環。
簡要題解:以每個位置i,都有一個最靠左的端點pre[i],滿足[pre[i],i]的所有字尾都滿足不形成奇環。因為原圖沒有偶環,是以隻要形成環就不滿足條件,問題簡單了許多。pre[i]是單調遞增的,故可以用整體二分來求。對于每組詢問,隻需要維護一個字首和就可以解決。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#define maxn 300010
using namespace std;
vector<int> v[maxn];
int f[maxn],pre[maxn],st[maxn];
bool vis[maxn];
long long sum1[maxn],sum2[maxn];
int n,m,T,top;
int find(int i)
{
if (f[i]==i) return i;
if (!vis[i]) st[++top]=i,vis[i]=;
return f[i]=find(f[i]);
}
void solve(int l,int r,int L,int R)
{
if (l>r) return;
if (L==R)
{
for (int i=l;i<=r;i++) pre[i]=L;
return;
}
int mid=(L+R)>>;
int ans=r+;
bool w=;
for (int i=mid;i<=r;i++)
{
int j=lower_bound(v[i].begin(),v[i].end(),mid)-v[i].begin();
for (;j<v[i].size();j++)
{
int f1=find(v[i][j]),f2=find(i);
if (f1!=f2)
{
f[f1]=f2;
if (!vis[f1]) st[++top]=f1,vis[f1]=;
}
else {w=;break;}
}
if (!w) {ans=i;break;}
}
while (top) f[st[top]]=st[top],vis[st[top]]=,top--;
solve(l,ans-,L,mid);solve(ans,r,mid+,R);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
v[max(x,y)].push_back(min(x,y));
}
for (int i=;i<=n;i++) sort(v[i].begin(),v[i].end());
for (int i=;i<=n;i++) f[i]=i;
solve(,n,,n);
//for (int i=1;i<=n;i++) printf("%d ",pre[i]);printf("\n");
for (int i=;i<=n;i++) sum1[i]=sum1[i-]+i,sum2[i]=sum2[i-]+(i-pre[i]+);
scanf("%d",&T);
while (T--)
{
int l,r;
scanf("%d%d",&l,&r);
long long ans=;
int now=upper_bound(pre+l,pre+r+,l)-pre;
//printf("%d\n",now);
ans=sum1[now-]-sum1[l-]-l*(now-l)*(l-)+sum2[r]-sum2[now-];
printf("%I64d\n",ans);
}
return ;
}
D.Weighting a Tree
題目大意:一個無向連通圖,每個點有-n到n的權值,構造一種方案,給每條邊指派,使每個點相鄰的邊的權值和等于這個點的權值。
簡要題解:如果這個圖是個二分圖,那麼無論如何指派,左右兩邊的和必然相等,則取原圖的一棵生成樹,隻使用樹邊來進行指派即可。如果原圖不是二分圖,我們可以找到一條連接配接同一部分的邊,那麼把這條邊的權值賦為兩部分差的一半即可。按照二分圖進行分類的方法,也是很厲害了。
<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#define maxn 100010
using namespace std;
int head[maxn],nxt[maxn*],to[maxn*],fa[maxn],fr[maxn];
int dep[maxn];
long long ans[maxn],w[maxn];
int n,m,num,e;
long long sum[];
void addedge(int x,int y)
{
num++;to[num]=y;nxt[num]=head[x];head[x]=num;
}
void dfs(int x)
{
sum[dep[x]&]+=w[x];
for (int p=head[x];p;p=nxt[p])
if (to[p]!=fa[x])
{
if (!dep[to[p]]) dep[to[p]]=dep[x]+,fa[to[p]]=x,fr[to[p]]=p,dfs(to[p]);
else if ((dep[x]-dep[to[p]]+)&) e=p;
}
}
void solve(int x)
{
for (int p=head[x];p;p=nxt[p])
if (fa[to[p]]==x) solve(to[p]),w[x]-=ans[p/];
ans[fr[x]/]=w[x];w[x]-=ans[fr[x]/];
}
int main()
{
num=;
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) scanf("%I64d",&w[i]);
for (int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y);addedge(y,x);
}
dep[]=;dfs();
if ((sum[]-sum[])&) {puts("NO");return ;}
if (!e && sum[]!=sum[]) {puts("NO");return ;}
if (e && sum[]!=sum[])
{
if (dep[to[e]]&) ans[e/]=(sum[]-sum[])/,sum[]=sum[];
else ans[e/]=(sum[]-sum[])/,sum[]=sum[];
w[to[e]]-=ans[e/];
w[to[e^]]-=ans[e/];
}
solve();
puts("YES");
for (int i=;i<=m;i++) printf("%I64d\n",ans[i]);
return ;
}