2018中国大学生程序设计竞赛 - 网络选拔赛
程序员文章站
2022-03-13 10:47:05
...
1001.Buy and Resell
思路:贪心,以前见过不少类型的,队友做的,直接上代码了;
代码:
#include<bits/stdc++.h>
using namespace std;
struct sell
{
long long int val;
bool operator<(const sell &aa)const
{
return val<aa.val;
}
};
multiset<sell>Sell,REsell;
multiset<sell>::iterator it,itt;
long long int ans,num;
int main()
{
long long t,i,j,n,x,now,next;
sell tt;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
Sell.clear();
REsell.clear();
ans=num=0;
for(i=0;i<n;i++)
{
scanf("%lld",&x);
if(REsell.size()!=0){
it=REsell.begin();
now=(*it).val;
//NOw=REsell.top().val;
if(Sell.size()!=0)
itt=Sell.begin();
if(now<x&&Sell.size()!=0&&(*itt).val<now)
{
num++;
ans+=x;
tt.val=x;
REsell.insert(tt);
Sell.erase(itt);
//printf("1ans=%lld num=%lld\n",ans,num);
}
else
if(now<x)
{
REsell.erase(it);
tt.val=now;
Sell.insert(tt);
ans-=2*now;
ans+=x;
tt.val=x;
REsell.insert(tt);
//printf("2ans=%lld num=%lld\n",ans,num);
}
else
if(Sell.size()!=0&&(*itt).val<x)
{
num++;
tt.val=x;
REsell.insert(tt);
ans+=x;
Sell.erase(itt);
}
else
{
tt.val=x;
Sell.insert(tt);
ans-=x;
//printf("5ans=%lld num=%lld\n",ans,num);
}
}
else
{
it=Sell.begin();
if(Sell.size()!=0&&(*it).val<x)
{
itt=Sell.begin();
num++;
ans+=x;
tt.val=x;
REsell.insert(tt);
Sell.erase(itt);
//printf("3ans=%lld num=%lld\n",ans,num);
}
else
{
tt.val=x;
Sell.insert(tt);
ans-=x;
//printf("4ans=%lld num=%lld\n",ans,num);
}
}
}
while(!Sell.empty())
{
it=Sell.begin();
ans+=(*it).val;
Sell.erase(it);
}
printf("%lld %lld\n",ans,num*2);
}
}
1003.Dream
思路:题解是费马小定理。。很优秀,但是自己推也能推出来,,因为等式左右两边都有加法操作,所以让加法矩阵全部为0 即可,然后又有p次方,保证0*0=0和1*0=0即刻,其他位置随意填,均可满足等式,但是题意还有要求,要存在q使得题意所述的两个集合相等,所以随意设定一个q(1<=q<=n-1),设定使其满足题意即可,最后就是某一列里有1--n-1个数字即可,我的是让q=1
代码:
#include<iostream>
#include<cstdio>
using namespace std;
int T,p;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&p);
for(int i=0;i<p;i++)
{
printf("0");
for(int j=1;j<p;j++)
printf(" 0");
printf("\n");
}
printf("0 0");
for(int i=2;i<p;i++)
printf(" 0");
printf("\n");
for(int i=1;i<p;i++)
{
if(i==p-1)
printf("0 1");
else
printf("0 %d",i+1);
for(int j=2;j<p;j++)
{
printf(" 1");
}
printf("\n");
}
}
}
1004.Find Integer
思路:数学方面的,传说中的费马大定理。。。,队友牛批
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=1000000000;
int n,a,b,c;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&a);
if(n==1)
{
printf("%d %d\n",1,a+1);
}else if(n==2){
int tn;
if(a&1)
{
tn=(a-1)/2;
b=2*tn*tn+2*tn;
c=2*tn*tn+2*tn+1;
}else{
tn=a/2;
b=tn*tn-1;
c=tn*tn+1;
}
printf("%d %d\n",b,c);
}else{
printf("%d %d\n",-1,-1);
}
}
return 0;
}
1009.Tree and Permutation
思路:简单图论,将每条边取出来 每次用到此边的情形是 当且仅当排列的相邻的两点分布在这条边的两边,也就是此边两边的点数的乘积,而每种情形即将这两点捆绑,有(n-1)!个排列中含有对应的情形,还有顺序,所以要乘以2,再乘上边的价值。
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define mod 1000000007
long long n,a[100005],X,Y,L,num,f[100005],ans;
long long IN[100005];
struct AA
{
long long v,next,l,k;
}pos[200005];
int dfs(int rt,int fa)
{
int v,numm=1;
for(int i=f[rt];i!=-1;i=pos[i].next)
{
v=pos[i].v;
if(fa==v) continue;
pos[i].k=0;
pos[i].k+=dfs(v,rt);
numm+=pos[i].k;
ans+=((((IN[n-1]*pos[i].l*2)%mod)*pos[i].k)%mod*(n-pos[i].k))%mod;
ans%=mod;
}
return numm;
}
int main()
{
IN[1]=1;
for(int i=2;i<=100000;i++)
{
IN[i]=IN[i-1]*i;
IN[i]%=mod;
}
while(~scanf("%lld",&n))
{
memset(f,-1,sizeof(f));
num=0;
ans=0;
for(int i=1;i<n;i++)
{
scanf("%lld%lld%lld",&X,&Y,&L);
pos[++num].v=Y;
pos[num].next=f[X];
pos[num].l=L;
f[X]=num;
pos[++num].v=X;
pos[num].next=f[Y];
pos[num].l=L;
f[Y]=num;
}
dfs(1,-1);
printf("%lld\n",ans);
}
}
1010.YJJ's Salesman
思路:线段树+dp,队友做的,就是维护左上的最优状态,每次取最大值,但是队友已经A了,那就线段树吧。。这个题就贡献 了,给大佬找了两组样例。。
代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define maxn 100010
using namespace std;
long long num[maxn];
long long dp[maxn];
struct point{
long long x;
long long y;
long long z;
}p[maxn];
bool cmp1(point a,point b){
if (a.x<b.x)return 1;
else if(a.x==b.x){
if(a.y<b.y)return 1;
return 0;
}
return 0;
}
bool cmp2(point a,point b){
if (a.y<b.y)return 1;
else if (a.y==b.y){
if (a.x<b.x)return 1;
return 0;
}
return 0;
}
struct xtree{
long long l,r;
long long maxx;
long long mid(){
return (l+r)/2;
}
}tree[4*maxn];
void pushup(long long id){
tree[id].maxx=max(tree[id*2].maxx,tree[id*2+1].maxx);
}
void build(long long id,long long l,long long r){
tree[id].l=l;
tree[id].r=r;
if (l==r){
tree[id].maxx=0;
return ;
}
long long mid=tree[id].mid();
build(id*2,l,mid);
build(id*2+1,mid+1,r);
pushup(id);
}
void update(long long id,long long pos,long long val){
if (tree[id].l==tree[id].r){
tree[id].maxx=max(val,tree[id].maxx);
return ;
}
long long mid=tree[id].mid();
if (pos<=mid){
update(id*2,pos,val);
}
else {
update(id*2+1,pos,val);
}
pushup(id);
}
long long query(long long id,long long l,long long r){
if (tree[id].l>=l&&tree[id].r<=r){
return tree[id].maxx;
}
long long mid=tree[id].mid();
if (r<=mid){
return query(id*2,l,r);
}
else if (l>mid){
return query(id*2+1,l,r);
}
else {
return max(query(id*2,l,mid),query(id*2+1,mid+1,r));
}
}
int main(){
long long t;
long long n;
long long i,j;
scanf("%lld",&t);
while (t--){
scanf("%lld",&n);
queue<long long>qq;
for (i=1;i<=n;i++)scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].z);
sort (p+1,p+n+1,cmp2);
num[p[1].y]=1;
for (i=2;i<=n;i++){
if (p[i].y!=p[i-1].y){
num[p[i].y]=num[p[i-1].y]+1;
}
}
build(1,1,num[p[n].y]);
sort (p+1,p+n+1,cmp1);
long long maxx=0;
p[0].x=0;
p[0].y=0;
p[0].z=0;
long long temp=0;
for (i=1;i<=n;i++){
if (p[i].x!=p[i-1].x){
while (!qq.empty()){
long long fuck=qq.front();
qq.pop();
update(1,num[p[fuck].y],dp[fuck]);
}
if (num[p[i].y]!=1){
dp[i]=p[i].z+query(1,1,num[p[i].y]-1);
}
else {
dp[i]=p[i].z;
}
qq.push(i);
}
else {
if (num[p[i].y]!=1){
dp[i]=p[i].z+query(1,1,num[p[i].y]-1);
}
else {
dp[i]=p[i].z;
}
qq.push(i);
}
if (dp[i]>maxx)maxx=dp[i];
}
printf("%lld\n",maxx);
}
}
推荐阅读
-
2019中国大学生程序设计竞赛-女生专场(重现赛)-1003 function
-
2019中国大学生程序设计竞赛-女生专场(重现赛)
-
Nested Triangles 2018 ACM-ICPC中国大学生程序设计竞赛
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 D 打篮球(java)
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 C 颜料的混合(java)
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛--I郊游(数学题)
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 E 233(java)
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 F 扫雷(java)
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 H-程序员的好印象【LIS】
-
2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 程序员的好印象