USACO 2004 U S Open

http://acm.pku.edu.cn/JudgeOnline/problem?id=1988
http://acm.pku.edu.cn/JudgeOnline/problem?id=1989
http://acm.pku.edu.cn/JudgeOnline/problem?id=1990
http://acm.pku.edu.cn/JudgeOnline/problem?id=1991
@@@@1@@@@
。。。想到了WHAT?黑书上的银河英雄传说么。。
小样。。穿上马甲我照样认出你阿。。。
#include<cstdio>
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=30000+100;
int F[maxn],D[maxn],S[maxn];
void set(int n)
{
REP(i,n) F[i]=i,D[i]=0,S[i]=1;
}
void find(int x)
{
if(x!=F[x])
find(F[x]),D[x]+=D[F[x]],F[x]=F[F[x]];
}
void Union(int x,int y)
{
find(x);find(y);
x=F[x];y=F[y];
F[x]=y;D[x]=S[y];S[y]+=S[x];
}
int main()
{
set(maxn);
int P;scanf("%d",&P);
char c;int a,b;
while(P–)
{
scanf("n%c",&c);
if(c==’M’)
scanf("%d %d",&a,&b),Union(a,b);
else
scanf("%d",&a),find(a),printf("%dn",D[a]);
}
}@@@@2@@@@
想了N久。。发现如果想要搞出所有n长的组合的话。。所有数必须能分成两部分。。
一部分能搞出所有n-1长的组合。。另一部分有1~k所有的数。。
又想了一会发现能分成n个包含1~k所有数的部分就能搞出所有n长的排列。。
所以直接上了。。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100000,maxk=10000;
bool e[maxk]={0};
int n,k;
int main()
{
cin>>n>>k;int t,l=k,ans=0;
for(int i=0;i<n;i++)
{
scanf("%d",&t);t–;
if(!e[t]) l–;
e[t]=true;
if(!l){memset(e,false,sizeof(e));l=k;ans++;}
}
cout<<ans+1<<endl;
}

代码短。。可是想的时间长阿。。。

@@@@3@@@@
从声音大的到声音小的算。。然后再一个个删。。
结果再用数状数组维护一下。。就OK了。。
#include<iostream>
#include<utility>
#include<algorithm>
#define low(i) (i&(-i))
using namespace std;
const int maxn=20000+100;
typedef long long LL;
int N,Pv[maxn],Px[maxn],Rx[maxn];
pair<int,int> A[maxn];
bool cmp1(const int&x,const int&y)
{
return A[x].first<A[y].first;
}
bool cmp2(const int&x,const int&y)
{
return A[x].second<A[y].second;
}
LL S[maxn]={0},C[maxn];
void add(LL C[],int l,int d)
{
for(;l<=N;l+=low(l))
C[l]+=d;
}
LL sum(LL C[],int l)
{
LL ans=0;
for(;l>0;l-=low(l))
ans+=C[l];
return ans;
}
LL sum(LL C[],int l,int r)
{
return sum(C,r)-sum(C,l-1);
}
int main()
{
cin>>N;
for(int i=1;i<=N;i++)
cin>>A[i].first>>A[i].second,Pv[i]=Px[i]=i;
sort(Pv+1,Pv+N+1,cmp1);
sort(Px+1,Px+N+1,cmp2);
for(int i=1;i<=N;i++)
{
Rx[Px[i]]=i;
add(C,i,1);
add(S,i,A[Px[i]].second);
}
LL ans=0;
for(int i=N;i>=1;i–)
{
int t=Pv[i],v=A[t].first,x=A[t].second,u=Rx[t];
ans+=(sum(C,1,u-1)*x-sum(S,1,u-1))*v;
ans+=(sum(S,u+1,N)-sum(C,u+1,N)*x)*v;
add(C,u,-1);
add(S,u,-x);
}
cout<<ans<<endl;
}@@@@4@@@@
这不是宋神牛交作业么?倒。。。
不会不会不会不会。。。写了个LJ贪心暴掉了。。。
@@@@Summary@@@@
2004的OPEN好easy阿。。。
我这种沙茶都搞定了3道。。。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>