首页 > 代码库 > Codeforces Round #261 (Div. 2)
Codeforces Round #261 (Div. 2)
第一场难得DIV2简单+AK人数多;
E:给出一张图,求最多的边数,满足:在这个边的集合中后面的边的权值大于前面的边;
思路:我们将图按权值排列,以为只可能边权值小的跟新权值大的所以对于一条边我们只跟新一次,所以是O(N);
1 #include<iostream> 2 #include<string> 3 #include<string.h> 4 #include<vector> 5 #include<algorithm> 6 #include<cstdio> 7 #define N 444444 8 struct node 9 {10 int u,v,w;11 };12 node e[N];13 14 int f[N],dp[N];15 using namespace std;16 int cmp(node a,node b){17 return a.w<b.w;18 }19 int main()20 {21 int n,m;22 scanf("%d%d",&n,&m);23 for (int i=1;i<=m;i++)24 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);25 sort(e+1,e+m+1,cmp);26 27 for (int i=1;i<=m;i++)28 {29 int j=i+1;30 while (e[j].w==e[i].w&&j<=m) j++;31 for (int k=i;k<j;k++) dp[e[k].v]=max(dp[e[k].v],dp[e[k].u]+1);32 i=j-1;33 }34 int ans=0;35 for (int i=1;i<=n;i++) ans=max(ans,dp[i]);36 printf("%d\n",ans);37 return 0;38 }
D:题目有点绕;
做法:我们先对HASH,求出两个数组L,R分别表示从左到右,从右到左:F(1,I,AI),F(J,N,AJ);
然后对于F[1,I,AI]求出I<J<=N中F[J,N,AJ]<F[1,I,AI]的个数;对于这种求区间的问题,树状数组就好。
我这里用map hash
然后我是从右往左的顺序统计的,做的时候脑残
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<string> 5 #include<iostream> 6 #include<vector> 7 #include<math.h> 8 #include<map> 9 #define inf 0x3f3f3f10 using namespace std;11 map<int,int>mp;12 map<int,int>mp2;13 typedef long long ll;14 int n;15 #define N 102345616 int a[N];17 int b[N];18 int c[N];19 int r[N];20 int l[N];21 int f[N];22 int lowbit(int x)23 {24 return x&(-x);25 }26 27 void update(int x)28 {29 while (x<=n)30 {31 f[x]+=1;32 x+=lowbit(x);33 }34 }35 36 ll sum(int x)37 {38 ll s=0;39 while (x)40 {41 s+=f[x];42 x-=lowbit(x);43 }44 return s;45 }46 47 int main()48 {49 scanf("%d",&n);50 mp.clear();51 mp2.clear();52 int t=0;53 for (int i=1;i<=n;i++) {54 scanf("%d",&a[i]);55 if (!mp[a[i]]) mp[a[i]]=++t;56 }57 58 for (int i=n;i>=1;i--)59 r[i]=b[mp[a[i]]]++;60 61 ll ans=0;62 for (int i=1;i<=n;i++)63 l[i]=c[mp[a[i]]]++;64 65 for (int i=1;i<=n;i++)66 {l[i]++;r[i]++;}67 68 //for (int i=1;i<=n;i++) cout<<l[i]<<" "<<r[i]<<endl;69 for (int i=n-1;i>=1;i--)70 {71 update(r[i+1]);72 ans+=sum(l[i]-1);73 //printf("%d\n",ans);74 }75 76 cout<<ans;77 return 0;78 }
C:还没看懂,好难^^
B:q求最大的差值,注意全相等的情况=N*(N-1)/2;
#include<string>#include<iostream>#include<vector>#include<math.h>#define inf 0x3f3f3fusing namespace std;int n;int a[823456];int main(){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]);; sort(a+1,a+n+1); int mm=a[n]; int m=a[1]; long long t1=0; long long t2=0; for (int i=1;i<=n;i++) { if (a[i]==mm)t1++; if (a[i]==m) t2++; } if (mm!=m) cout<<mm-m<<" "<<t1*t2<<endl; else { long long t1=n; cout<<mm-m<<" "<<t1*(t1-1)/2<<endl; } return 0;}
A:正方形。。
乱搞,HACK点居多,当点在一条线上,分别考虑
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<string> 5 #include<iostream> 6 #include<vector> 7 #include<math.h> 8 #define inf 0x3f3f3f 9 using namespace std;10 int n;11 int main()12 {13 int x1,x2,yy1,y2;14 cin>>x1>>yy1>>x2>>y2;15 16 if (x1==x2&&yy1==y2) {cout<<-1<<endl;return 0;}17 if (x1!=x2&&yy1!=y2){18 if (abs(y2-yy1)!=abs(x1-x2))19 {20 cout<<-1;21 return 0;22 }23 cout<<x1<<" "<<y2<<" "<<x2<<" "<<yy1<<endl;24 return 0;25 }26 27 if (yy1>y2) swap(yy1,y2);28 if (x1==x2)29 {30 int b=y2-yy1;31 cout<<x1+b<<" "<<yy1<<" "<<x2+b<<" "<<yy1+b<<endl;32 return 0;33 }34 else35 {36 if (x1>x2) swap(x1,x2);37 int b=x2-x1;38 cout<<x1<<" "<<yy1+b<<" "<<x2<<" "<<yy1+b<<endl;39 return 0;40 }41 return 0;42 }
终于出了灰的坑
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。