[JSOI2008]星球大战starwar 【并差集】【逆序处理】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1015
【算法分析】
就是逆过来，把拆分变成合并，用并差集即可。
【其它】= =1RE。n<=2m我还以为是他搞错了压在一起。。。
【CODE】
#include #include #include using namespace std;
const int N=405555;
struct edge{int y;edge *next;}g[405555],*ls[N];
int n,m,ans,e,Qn;
int F[N],Num[N],Q[N],v[N],reply[N];

inline void addedge(int x,int y){
g[++e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}

int GF(int k){
int res,i,tmp;
for (i=k;F[i]!=i;i=F[i]);
res=i;
for (i=k;F[i]!=i;tmp=F[i],F[i]=res,i=tmp);
return res;
}

int main(){
e=0;
memset(ls,0,sizeof(ls));
memset(v,0,sizeof(v));
int x,y,i;
scanf("%d%d",&n,&m);
for (i=0;i scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
for (i=0;i F[i]=i;
Num[i]=1;
}
scanf("%d",&Qn);
ans=n;
for (i=0;i scanf("%d",&Q[i]);
if (!v[Q[i]]) ans–;
v[Q[i]]++;
}
for (i=0;i for (edge *t=ls[i];t;t=t->next)
if (!v[t->y] && GF(i)!=GF(t->y)){
ans–;
x=F[i]; y=F[t->y];
if (Num[x]>Num[y]) swap(x,y);
F[x]=y;
Num[y]+=Num[x];
}
reply[Qn]=ans;
for (i=Qn-1;i>=0;i–){
v[Q[i]]–;
if (!v[Q[i]]){
ans++;
for (edge *t=ls[Q[i]];t;t=t->next)
if (!v[t->y] && GF(Q[i])!=GF(t->y)){
ans–;
x=F[Q[i]]; y=F[t->y];
if (Num[x]>Num[y]) swap(x,y);
F[x]=y;
Num[y]+=Num[x];
}
}
reply[i]=ans;
}
for (int i=0;i<=Qn;i++) printf("%dn",reply[i]);
}

[JSOI2008]球形空间产生器sphere 【高斯消元】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1013
【题目大意】
求高维球心坐标。
【算法分析】
首先距离公式容易推知，然后点到球心距离必然都相等，于是联立n条等式，高斯消元即可。
另外：
我爬山法好像陷进局部最优解里去了，我爬山用的是方差作估价函数，直接WA。
估计最后一名的800+MS的神牛就是爬山过的。求爬山正确的估价函数。
【其它】高斯消元1Y。
【CODE】
#include #include #include #include #define sqr(x) ((x)*(x))
const int N=15;
int n;
double a[N][N],c[N][N];

void Swap(int x,int y){
double tmp;
for (int i=0;i<=n;i++){
tmp=c[x][i];
c[x][i]=c[y][i];
c[y][i]=tmp;
}
}

void guass(){
int i,j,k;
for (i=1;i<=n;i++){
for (k=i,j=i;j<=n;j++)
if (fabs(c[j][i-1])>fabs(c[k][i-1])) k=j;
Swap(i,k);
for (j=i+1;j<=n;j++)
for (k=n;k>=i-1;k–)
c[j][k]-=c[i][k]*c[j][i-1]/c[i][i-1];
}
}

void solve(){
double ans[N];
memset(ans,0,sizeof(ans));
ans[n]=1;
for (int i=n;i>=1;i–){
double Sum=0;
for (int j=i;j<=n;j++)
Sum-=ans[j]*c[i][j];
ans[i-1]=Sum/c[i][i-1];
}
for (int i=0;i if (i) printf(" ");
printf("%.3lf",ans[i]);
}
printf("n");
}

int main(){
scanf("%d",&n);
for (int i=0;i<=n;i++)
for (int j=0;j scanf("%lf",&a[i][j]);
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++){
for (int j=0;j c[i][j]=2*(a[i][j]-a[i-1][j]);
c[i][n]+=sqr(a[i-1][j])-sqr(a[i][j]);
}
}
guass();
solve();
}

[JSOI2008]最大数maxnumber 【线段树】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1012
【算法分析】
线段树，会的人都知道。。。
【其它】1Y。用cin果断跑到几乎最慢
【做题原因】邻近省选，练练手，刷出1Y，刷出自信。
【CODE】
#include #include #include #include using namespace std;
const int INF=0x7FFFFFFF;
struct Node{int l,r,key;}Tr[1000000];
int m,mod,n,ans;

void build(int p,int l,int r){
Tr[p].l=l; Tr[p].r=r; Tr[p].key=-INF;
if (l int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
}

void Add(int p,int t,int key){
if (Tr[p].l==Tr[p].r){
Tr[p].key=key;
return;
}
if (t<=(Tr[p].l+Tr[p].r)/2) Add(p*2,t,key);
else Add(p*2+1,t,key);
Tr[p].key=max(Tr[p*2].key,Tr[p*2+1].key);
}

void Get(int p,int l,int r){
if (l<=Tr[p].l && Tr[p].r<=r){
ans=max(ans,Tr[p].key);
return;
}
int mid=(Tr[p].l+Tr[p].r)/2;
if (l<=mid) Get(p*2,l,r);
if (r> mid) Get(p*2+1,l,r);
}

int main(){
ios::sync_with_stdio(false);
ans=n=0;
cin >> m >> mod;
build(1,1,m);
for (int i=1;i<=m;i++){
char ch; __int64 x;
cin >> ch >> x;
if (ch==’A’){
x=(x+ans)%mod;
n++;
Add(1,n,(int)(x));
}
else{
ans=-INF;
Get(1,n-x+1,n);
cout << ans << "n";
}
}
}

[HDOJ3335 Divisibility]【DAG图的最大独立集】【最大反链】【最小链划分】【最小路径覆盖】

【题目大意】
给定N个数，让你取最多的数，使得取出的数里，不存在A是B的倍数这种情况。
【算法分析】
虽然当时ACM_DIY群赛时蒙对了算法，当时推理方式见（那叫一个强力）：
http://hi.baidu.com/edwardmj/blog/item/1ae99b3f5f5cbee53d6d9789.html
但一直没有理解，于是今天重温二分图时回来做了一下。
本题可以先把相同的数去掉，然后若A为B的倍数，那么B->A。
由于A>B，那么是一个DAG图（有向无环图）
然后DAG图的最大反链就可以利用匹配来搞。（传递闭包后的DAG图的最大独立集=最大反链）
具体做法是每个点拆两个点，弄成二分图，然后匹配。最后输出n-匹配数。
二分图总结见：http://hi.baidu.com/edwardmj/blog/item/b5fc0419bd3661f1af513325.html
小菜总结，不足谢谢补充。
【CODE】
#include #include #include const int N=1005;
typedef __int64 lld;
struct edge{int y;edge *next;}g[1005555],*ls[N];
int n,e,cnt;
int v[N],link[N];
lld a[N];

int cmp(const void *A,const void *B){
lld AA=*((lld*)A),BB=*((lld*)B);
if (AA>BB) return 1;
if (AA return 0;
}

void addedge(int x,int y){
g[++e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}

void build(){
int tot=0,i,j;
for (i=1;i<=n;i++)
if (!tot || a[i]!=a[tot])
a[++tot]=a[i];
n=tot;
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
if (a[j]%a[i]==0 && a[j]>a[i])
addedge(i,j);
}

bool Find(int p){
for (edge *t=ls[p];t;t=t->next)
if (v[t->y]!=cnt){
v[t->y]=cnt;
int q=link[t->y];
link[t->y]=p;
if (!q || Find(q)) return true;
link[t->y]=q;
}
return false;
}

void solve(){
memset(link,0,sizeof(link));
memset(v,0,sizeof(v));
int ans=0;
for (cnt=1;cnt<=n;cnt++)
if (Find(cnt)) ans++;
printf("%dn",n-ans);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (;Tc;Tc–){
scanf("%d",&n);
e=0;
for (int i=1;i<=n;i++){
scanf("%I64d",&a[i]);
ls[i]=NULL;
}
qsort(a+1,n,sizeof(lld),cmp);
build();
solve();
}
}

[衡阳八中1457 棋盘游戏]【博弈】【SG函数】【NIM和】【任意一子游戏到达终态结束的游戏】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1457
【算法分析】
首先，n个皇后是独立的，于是我们联想到利用SG函数来求解。
但是它与传统NIM游戏又有所不同，它是任意一个子游戏到达终态，那么就结束游戏。
好的，现在两个家伙都是绝顶聪明的。
于是他们肯定不会主动去走这样的一步：走完以后，该皇后x==0 || y==0 || x==y。
因为走完这步以后，对方就赢了，我们定义这种行为为沙茶。
因为他们都不会主动沙茶，那么就只能被沙茶。
也就是说所有的皇后的下一步都是令他沙茶的，那么才会真沙茶。
于是我们可以定义，下一步只能做沙茶的点为终态。
那么如果所有子游戏都到达终态，这时候先手必败。
这又刚好与传统NIM游戏一样了~
于是我们只要在计算SG函数时忽略x==0 || y==0 || x==y的点，那么就可以得我们定义所对应的SG函数值。
然后再利用那个Sprague-Grundy Theorem，再加上暴力计算SG函数，顺利解决本题。
【其它】1WA。注意那个SG函数的值好像是可能超100的= =。。。改大了瞬间AC。
【CODE】
#include #include #include #define flag(x,y) (!(!(x) || !(y) || (x)==(y)))
int SG[100][100];
bool v[100][100][205];

void Cal_SG(){
int i,j,k;
for (i=1;i<100;i++)
for (j=1;j<100;j++)
if (flag(i,j)){
for (k=1;i>=k || j>=k;k++){
if (i>=k && flag(i-k,j)) v[i][j][SG[i-k][j]]=true;
if (j>=k && flag(i,j-k)) v[i][j][SG[i][j-k]]=true;
if (i>=k && j>=k && flag(i-k,j-k))
v[i][j][SG[i-k][j-k]]=true;
}
for (k=0;k<=200;k++)
if (!v[i][j][k]){
SG[i][j]=k;
break;
}
}
}

inline void output(int x){
if (!x) puts("T_T");
else puts("^o^");
}

int main(){
int Tc,n,i,x,y,ans,check;
Cal_SG();
scanf("%d",&Tc);
for (;Tc;Tc–){
scanf("%d",&n);
ans=check=0;
for (i=1;i<=n;i++){
scanf("%d%d",&x,&y);
if (!x && !y) check=2;
if (!flag(x,y) && !check) check=1;
ans^=SG[x][y];
}
switch (check){
case 0:output(ans); break;
case 1:output(1); break;
case 2:output(0); break;
}
}
}