{"id":44,"date":"2009-11-27T16:44:00","date_gmt":"2009-11-27T08:44:00","guid":{"rendered":"http:\/\/localhost\/?p=44"},"modified":"2009-11-27T16:44:00","modified_gmt":"2009-11-27T08:44:00","slug":"usaco_2004_u_s_open","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=44","title":{"rendered":"USACO 2004 U S Open"},"content":{"rendered":"

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@@@@
\u3002\u3002\u3002\u60f3\u5230\u4e86WHAT\uff1f\u9ed1\u4e66\u4e0a\u7684\u94f6\u6cb3\u82f1\u96c4\u4f20\u8bf4\u4e48\u3002\u3002
\u5c0f\u6837\u3002\u3002\u7a7f\u4e0a\u9a6c\u7532\u6211\u7167\u6837\u8ba4\u51fa\u4f60\u963f\u3002\u3002\u3002
#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<\/a>("%dn",D[a]);
}
}@@@@2@@@@
\u60f3\u4e86N\u4e45\u3002\u3002\u53d1\u73b0\u5982\u679c\u60f3\u8981\u641e\u51fa\u6240\u6709n\u957f\u7684\u7ec4\u5408\u7684\u8bdd\u3002\u3002\u6240\u6709\u6570\u5fc5\u987b\u80fd\u5206\u6210\u4e24\u90e8\u5206\u3002\u3002
\u4e00\u90e8\u5206\u80fd\u641e\u51fa\u6240\u6709n-1\u957f\u7684\u7ec4\u5408\u3002\u3002\u53e6\u4e00\u90e8\u5206\u67091\uff5ek\u6240\u6709\u7684\u6570\u3002\u3002
\u53c8\u60f3\u4e86\u4e00\u4f1a\u53d1\u73b0\u80fd\u5206\u6210n\u4e2a\u5305\u542b1~k\u6240\u6709\u6570\u7684\u90e8\u5206\u5c31\u80fd\u641e\u51fa\u6240\u6709n\u957f\u7684\u6392\u5217\u3002\u3002
\u6240\u4ee5\u76f4\u63a5\u4e0a\u4e86\u3002\u3002\u3002
#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;
}<\/p>\n

\u4ee3\u7801\u77ed\u3002\u3002\u53ef\u662f\u60f3\u7684\u65f6\u95f4\u957f\u963f\u3002\u3002\u3002<\/p>\n

@@@@3@@@@
\u4ece\u58f0\u97f3\u5927\u7684\u5230\u58f0\u97f3\u5c0f\u7684\u7b97\u3002\u3002\u7136\u540e\u518d\u4e00\u4e2a\u4e2a\u5220\u3002\u3002
\u7ed3\u679c\u518d\u7528\u6570\u72b6\u6570\u7ec4\u7ef4\u62a4\u4e00\u4e0b\u3002\u3002\u5c31OK\u4e86\u3002\u3002
#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@@@@
\u8fd9\u4e0d\u662f\u5b8b\u795e\u725b\u4ea4\u4f5c\u4e1a\u4e48\uff1f\u5012\u3002\u3002\u3002
\u4e0d\u4f1a\u4e0d\u4f1a\u4e0d\u4f1a\u4e0d\u4f1a\u3002\u3002\u3002\u5199\u4e86\u4e2aLJ\u8d2a\u5fc3\u66b4\u6389\u4e86\u3002\u3002\u3002
@@@@Summary@@@@
2004\u7684OPEN\u597deasy\u963f\u3002\u3002\u3002
\u6211\u8fd9\u79cd\u6c99\u8336\u90fd\u641e\u5b9a\u4e863\u9053\u3002\u3002\u3002 <\/p>\n","protected":false},"excerpt":{"rendered":"

http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=1988http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=1989http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=1990http:\/\/acm.pku.edu.cn\/JudgeOnline\/problem?id=1991@@@@1@@@@\u3002\u3002\u3002\u60f3\u5230\u4e86WHAT\uff1f\u9ed1\u4e66\u4e0a\u7684\u94f6\u6cb3\u82f1\u96c4\u4f20\u8bf4\u4e48\u3002\u3002\u5c0f\u6837\u3002\u3002\u7a7f\u4e0a\u9a6c\u7532\u6211\u7167\u6837\u8ba4\u51fa\u4f60\u963f\u3002\u3002\u3002#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@@@@\u60f3\u4e86N\u4e45\u3002\u3002\u53d1\u73b0\u5982\u679c\u60f3\u8981\u641e\u51fa\u6240\u6709n\u957f\u7684\u7ec4\u5408\u7684\u8bdd\u3002\u3002\u6240\u6709\u6570\u5fc5\u987b\u80fd\u5206\u6210\u4e24\u90e8\u5206\u3002\u3002\u4e00\u90e8\u5206\u80fd\u641e\u51fa\u6240\u6709n-1\u957f\u7684\u7ec4\u5408\u3002\u3002\u53e6\u4e00\u90e8\u5206\u67091\uff5ek\u6240\u6709\u7684\u6570\u3002\u3002\u53c8\u60f3\u4e86\u4e00\u4f1a\u53d1\u73b0\u80fd\u5206\u6210n\u4e2a\u5305\u542b1~k\u6240\u6709\u6570\u7684\u90e8\u5206\u5c31\u80fd\u641e\u51fa\u6240\u6709n\u957f\u7684\u6392\u5217\u3002\u3002\u6240\u4ee5\u76f4\u63a5\u4e0a\u4e86\u3002\u3002\u3002#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; […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/44"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=44"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/44\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=44"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=44"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=44"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}