BUPT2014新生暑假个人排位赛08

2024-08-24 12:18

本文主要是介绍BUPT2014新生暑假个人排位赛08,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

BOJ 448 游戏

计算几何
枚举每一条边,如果该边两侧的角有至少一个钝角,则计数
<pre name="code" class="cpp">#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define eps 1e-9using namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}//-----------------------------------------------------------------------
typedef long long ll;struct point
{double x,y;point(){}point(double a,double b):x(a),y(b){}friend point operator - (const point &a,const point &b){return point(a.x-b.x,a.y-b.y);}
}a[1010];double dot(const point &a,const point &b)
{return a.x*b.x+a.y*b.y;
}int main()
{int n;while(read(n)){for(int i=1;i<=n;i++){scanf("%lf %lf",&a[i].x,&a[i].y);}a[n+1]=a[1];a[0]=a[n];a[n+2]=a[2];int ans=0;for(int i=1;i<=n;i++){point temp1=a[i+2]-a[i+1],temp2=a[i-1]-a[i];point temp=a[i+1]-a[i];//   a[ i ]   a[ i+1 ]  edgeif(dot(temp,temp2)<-eps||dot(temp,temp1)>eps)ans++;}printf("%d\n",ans);}return 0;
}

 

BOJ 468 小妹妹送快递

用所有的非DAG最短路都行,用最小生成树也行
最短路的松弛操作改成    dist[ next ] = min( dist[ next] , max( dist[ pre ] , e[ pre ][ next ].value ) )
Kruskal算法只需要维护到  fa[ 1 ] == fa[ n ]的情况,prim貌似维护完之后还要dfs遍历一次(而且我写的prim超时了)
SPFA版本
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define INF 0x3f3f3f3fusing namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}//-----------------------------------------------------------------------const int MAXN=10010;
const int MAXE=100010;struct Edge
{int to,next;int v;
}e[2*MAXE];
int head[MAXN],tot=0,dist[MAXN];
bool vis[MAXN];int n,m;void addedge(int u,int v,int w)
{e[tot].to=v;e[tot].v=w;e[tot].next=head[u];head[u]=tot++;
}void spfa()
{queue<int> que;que.push(1);vis[1]=true;dist[1]=0;while(!que.empty()){int u=que.front();que.pop();for(int i=head[u];i!=-1;i=e[i].next){int maxn=max(e[i].v,dist[u]);if(dist[e[i].to]>maxn){dist[e[i].to]=maxn;if(!vis[e[i].to]){vis[e[i].to]=true;que.push(e[i].to);}}}vis[u]=false;}
}int main()
{int T;read(T);while(T--){read(n);read(m);tot=0;memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(dist,INF,sizeof(dist));int u,v,w;for(int i=1;i<=m;i++){read(u);read(v);read(w);if(u==1||v==n)addedge(u,v,w);else if(u==n||v==1)addedge(v,u,w);else{addedge(u,v,w);addedge(v,u,w);}}
/*      for(int i=1;i<=n;i++){cout<<i<<" : ";for(int j=head[i];j!=-1;j=e[j].next)cout<<e[j].to<<" ";cout<<endl;}
*/spfa();if(dist[n]==0)printf("%d\n",1);else if(dist[n]==INF)printf("shimatta!\n");elseprintf("%d\n",dist[n]);}return 0;
}

Kruskal版本
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define eps 1e-9
#define INF 0x3f3f3f3fusing namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}//-----------------------------------------------------------------------const int MAXN=100010;struct Edge
{int u,v,w;
}e[MAXN];int n,m;
int fa[10010];int find_fa(int x)
{if(fa[x]==x)return x;elsereturn fa[x]=find_fa(fa[x]);
}void Merge(int x,int y)
{fa[x]=y;
}bool cmp(Edge a,Edge b)
{return a.w<b.w;
}int Kruskal()
{sort(e+1,e+m+1,cmp);for(int i=1;i<=m;i++){int xx=find_fa(e[i].u);int yy=find_fa(e[i].v);if(xx!=yy){Merge(xx,yy); if(find_fa(1)==find_fa(n))return e[i].w;}}if(find_fa(1)!=find_fa(n))return INF;
}int main()
{int T;read(T);while(T--){read(n),read(m);for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++)read(e[i].u),read(e[i].v),read(e[i].w);int temp=Kruskal();if(temp==0)printf("1\n");else if(temp==INF)printf("shimatta!\n");elseprintf("%d\n",temp);}return 0;
}

BOJ 472 学姐点名

签到题
卡代码长度,所以用了C写
将1~n求和,再将输入的 n-1个数求和,相减则是正确答案
#include<stdio.h>main()
{long long n;while(~scanf("%lld",&n)){long long sum=n,temp,i;for(i=1;i<n;i++){scanf("%lld",&temp);sum+=i-temp;}printf("%lld\n",sum);}
}


BOJ 452 解码锦标赛

DP
简直不敢相信的状态转移   i 表示第 i 个人, dep 表示第 dep 场比赛, dp 值表示胜利概率
dp[ i ][ dep ] = dp[ i ][ dep ] * sigma ( a[ i ][ j ]*dp[ j ][ dep-1 ] ) 其中 j 表示的在第 dep 场比赛可能与 i 碰面的队伍 ( j 的范围见代码
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define EPS 1e-10
#define INF 0x3f3f3f3fusing namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}//-----------------------------------------------------------------------const int MAXN=300;int n;
double a[MAXN][MAXN];double dp[MAXN][10];//winvoid solve(int dep)
{int N=1<<dep;N/=2;for(int i=1;i<=n;i++){int k=(i-1)/N;double temp=0;//cout<<i<<" :";if(k&1){for(int j=(k-1)*N+1;j<=k*N;j++){temp+=a[i][j]*dp[j][dep-1];//cout<<j<<" "<<dp[j][dep-1]<<" ";}//cout<<endl;}else{for(int j=(k+1)*N+1;j<=(k+2)*N;j++){temp+=a[i][j]*dp[j][dep-1];//cout<<j<<" "<<dp[j][dep-1]<<" ";}//cout<<endl;}dp[i][dep]=dp[i][dep-1]*temp;}
}int main()
{//   freopen("data.txt","r",stdin);while(read(n)&&n){int N=n,po=0;double maxn=-1.0;n=1<<n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lf",&a[i][j]);for(int i=1;i<=n;i++){if(i&1)dp[i][1]=a[i][i+1];elsedp[i][1]=a[i][i-1];//cout<<" "<<dp[i][1];}//cout<<endl;for(int i=2;i<=N;i++)solve(i);for(int i=1;i<=n;i++){//cout<<dp[i][N]<<endl;if((dp[i][N]-maxn)>EPS){maxn=dp[i][N];po=i;}}printf("%d\n",po);}return 0;
}

BOJ 451 田田的算数题

用线段树维护首项 x 与 公差 d
如果 首项 被截断在某一段区间外,而1操作修改又覆盖到了改区间,则将恰好被截断的那一部分即 x + ( mid - l + 1 ) * d 作为首项

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define eps 1e-9
#define INF 0x3f3f3f3f
#define ll long longusing namespace std;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int MAXN=100010;struct Node
{ll l,r;ll sum;ll x,d;      //x表示首项 , d表示公差
}a[8*MAXN];int n,m,num[MAXN];void build(int idx, ll l, ll r)
{a[idx].l=l,a[idx].r=r;a[idx].sum=a[idx].x=a[idx].d=0;if(l==r){a[idx].sum=num[l];return;}ll mid=l+((r-l)>>1);build(idx<<1,l,mid);build(idx<<1|1,mid+1,r);a[idx].sum=a[idx<<1].sum+a[idx<<1|1].sum;
}void pushdown(int idx)
{ll l=a[idx].l,r=a[idx].r;ll lc=idx<<1,rc=idx<<1|1,mid=l+((r-l)>>1);a[lc].x+=a[idx].x;a[rc].x+=a[idx].x+(mid-l+1)*a[idx].d;a[lc].d+=a[idx].d;a[rc].d+=a[idx].d;a[idx].sum+=a[idx].x*(r-l+1);a[idx].sum+=(r-l+1)*(r-l)/2*a[idx].d;a[idx].x=a[idx].d=0;
}//如果标记相同则下推
void update(int idx,ll L,ll R,int x,int d)
{ll l=a[idx].l,r=a[idx].r;ll lc=idx<<1,rc=idx<<1|1,mid=l+((r-l)>>1);if(l==L&&r==R){a[idx].x+=x;a[idx].d+=d;return;}pushdown(idx);                //标记下放同时更新if(R<=mid)  update(lc,L,R,x,d);else if(L>mid)  update(rc,L,R,x,d);else{update(lc,L,mid,x,d);update(rc,mid+1,R,x+d*(mid-L+1),d);}a[idx].sum+=x*(R-L+1)+(R-L+1)*(R-L)/2*d;
}ll query(int idx,int L,int R)
{ll l=a[idx].l,r=a[idx].r;ll mid=l+((r-l)>>1);ll ret=(a[idx].x*2+(L+R-l*2)*a[idx].d)*(R-L+1)/2;if(l==L&&r==R){pushdown(idx);return a[idx].sum;}if(R<=mid)return ret+query(idx<<1,L,R);if(L>mid)return ret+query(idx<<1|1,L,R);return ret+query(idx<<1,L,mid)+query(idx<<1|1,mid+1,R);
}int main()
{int T,t,l,r,x,d;read(T);while(T--){read(n),read(m);for(int i=1;i<=n;i++)read(num[i]);build(1,1,n);
/*        for(int i=1;i<=2*n+1;i++)printf("%d : (%d->%d)  %d\n",i,a[i].l,a[i].r,a[i].sum);*/while(m--){read(t),read(l),read(r);if(t==1){read(x),read(d);update(1,l,r,x,d);/*               for(int i=1;i<=2*n+1;i++)printf("%d : (%d->%d)  %d\n",i,a[i].l,a[i].r,a[i].sum);*/}else{ll ans=query(1,l,r);write(ans);putchar('\n');}}}return 0;
}

下面为桶分法的代码
将 1~n 区间按照 sqrt( n )的大小分块
在整块内就统一加减,用同样的方法维护 x 和 d ,然后边缘部分暴力加
感谢 刘玮 的代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAX_N 100005
using namespace std;
typedef long long LL;
const int sib=100;
int N,M;
LL A[100005],B[1000],Bhead[1000],Bdif[1000];
void add(int a,int b,LL x,LL d)
{int i,j;int bl=a/sib,br=b/sib;
//  a=a%sib;
//  b=b%sib;LL res=0;for(i=a; i<bl*sib+sib&&i<=b; i++){A[i]=A[i]+x+(i-a)*d;B[i/sib]+=x+(i-a)*d;res+=d;}
//   printf("%d %d res:%lld\n",a,i-1,res);//printf("res:%lld\n",res);for(j=bl+1; j<br; j++){Bhead[j]=Bhead[j]+x+res;Bdif[j]=Bdif[j]+d;B[j]+=(x+res)*sib+sib*(sib-1)/2*d;//   printf("%d %d\n",x+res,sib);// printf("add B[%d] :%lld\n",j,(x+res)*sib+sib*(sib-1)/2*d);res+=sib*d;//  printf("Bhead[%d]=%d ",j,Bhead[j]);//  printf("Bdif[%d]=%d\n",j,Bdif[j]);}// printf("tail:%d %d res:%d\n",br*sib,b,res);if(bl!=br)for(i=br*sib; i<=b; i++){B[i/sib]+=x+d*(i-a);A[i]+=x+d*(i-a);//  printf("add:A[%d]=%lld\n",i,A[i]);}
}
LL sum(int a,int b)
{int i,j;int bl=a/sib,br=b/sib;LL res=0;for(i=a; i<(bl+1)*sib&&i<=b; i++){// printf("A[%d]=%lld ",i,A[i]);res+=A[i];//  printf("B:%lld\n",Bhead[bl]+(i%sib)*Bdif[bl]);res+=Bhead[bl]+(i%sib)*Bdif[bl];}for(i=bl+1; i<br; i++){// printf("B[%d]:%lld\n",i,B[i]);res+=B[i];}// printf("l:%d r:%d\n",bl,br);if(br!=bl)for(i=br*sib; i<=b; i++){res+=A[i];//   printf("A[%d]=%lld ",i,A[i]);res+=Bhead[br]+(i%sib)*Bdif[br];//  printf("B:%lld\n",Bhead[br]+(i%sib)*Bdif[br]);}return res;
}
int main()
{int i,j,k,T,l,r,flag,x,d;scanf("%d",&T);while(T--){scanf("%d%d",&N,&M);memset(B,0,sizeof(B));memset(Bhead,0,sizeof(Bhead));memset(Bdif,0,sizeof(Bdif));for(i=0; i<N; i++){scanf("%lld",&A[i]);B[i/sib]+=A[i];}for(i=0; i<M; i++){scanf("%d %d %d",&flag,&l,&r);if(flag==1){scanf("%d %d",&x,&d);add(l-1,r-1,(LL)x,(LL)d);/* for(j=0;j<N/sib;j++){printf("B[%d]=%lld ",j,B[j]);}printf("\n");*/}else if(flag==2){/*for(j=0;j<N/sib;j++){printf("B[%d]=%lld ",j,B[j]);}printf("\n");*/printf("%lld\n",sum(l-1,r-1));}//  printf("flag:%d\n",flag);}}return 0;
}
树状数组版
感谢楠哥的代码提供
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#define N 100005
using namespace std;
typedef long long ll;
ll ans;
ll A[N],B[N],C[N],D[N],E[N];
ll n;ll lowbit(ll x)
{return x&(-x);
}void Update(ll x,ll det,ll a[])
{for (ll i = x;i<= n; i+=lowbit(i))a[i]+=det;
}ll GetSum(ll x,ll a[])
{ll res=0;for (ll i=x;i>0;i-=lowbit(i))res+=a[i];return res;
}ll dGetSum(ll n)
{ll res=0;res=(n+1)*(n+1)*GetSum(n,C)+((n+1)*GetSum(n-1,D)-(3*n+4)*GetSum(n,D)+GetSum(n,E)-n*(n+1)*GetSum(n-1,C))/2;return res;}ll xGetSum(ll n)
{ll res=0;res=(n+1)*GetSum(n,A)-GetSum(n,B);return res;
}
int main()
{int T;cin>>T;while(T--){ll m,num1=0;scanf("%lld%lld",&n,&m);memset(A,0,sizeof(long long)*(n+2));memset(B,0,sizeof(long long)*(n+2));memset(C,0,sizeof(long long)*(n+2));memset(D,0,sizeof(long long)*(n+2));memset(E,0,sizeof(long long)*(n+2));for (ll i=1;i<=n;i++){ll num;scanf("%lld",&num);Update(i,num-num1,A);Update(i,i*(num-num1),B);num1=num;}for (ll i=1;i<=m;i++){ll order;scanf("%d",&order);if ( order==1 ){ll l,r,x,d;scanf("%lld%lld%lld%lld",&l,&r,&x,&d);Update(l,x,A);Update(l,l*x,B);Update(r+1,-x,A);Update(r+1,-(r+1)*x,B);if (r>l){Update(l+1,d,C);Update(r+1,-(r-l+1)*d,C);Update(r+2,(r-l)*d,C);Update(l+1,(l+1)*d,D);Update(r+1,-(r-l+1)*(r+1)*d,D);Update(r+2,(r-l)*(r+2)*d,D);Update(l+1,(l+1)*(l+1)*d,E);Update(r+1,-(r+1)*(r+1)*(r-l+1)*d,E);Update(r+2,(r-l)*(r+2)*(r+2)*d,E);}}else if( order==2 ){ll l,r;scanf("%lld%lld",&l,&r);ans=xGetSum(r)-xGetSum(l-1)+dGetSum(r)-dGetSum(l-1);printf("%lld\n",ans);}}}
}



这篇关于BUPT2014新生暑假个人排位赛08的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1102456

相关文章

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

HomeBank:开源免费的个人财务管理软件

在个人财务管理领域,找到一个既免费又开源的解决方案并非易事。HomeBank&nbsp;正是这样一个项目,它不仅提供了强大的功能,还拥有一个活跃的社区,不断推动其发展和完善。 开源免费:HomeBank 是一个完全开源的项目,用户可以自由地使用、修改和分发。用户友好的界面:提供直观的图形用户界面,使得非技术用户也能轻松上手。数据导入支持:支持从 Quicken、Microsoft Money

分布式系统的个人理解小结

分布式系统:分的微小服务,以小而独立的业务为单位,形成子系统。 然后分布式系统中需要有统一的调用,形成大的聚合服务。 同时,微服务群,需要有交流(通讯,注册中心,同步,异步),有管理(监控,调度)。 对外服务,需要有控制的对外开发,安全网关。

Java IO 操作——个人理解

之前一直Java的IO操作一知半解。今天看到一个便文章觉得很有道理( 原文章),记录一下。 首先,理解Java的IO操作到底操作的什么内容,过程又是怎么样子。          数据来源的操作: 来源有文件,网络数据。使用File类和Sockets等。这里操作的是数据本身,1,0结构。    File file = new File("path");   字

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

Science|癌症中三级淋巴结构的免疫调节作用与治疗潜力|顶刊精析·24-09-08

小罗碎碎念 Science文献精析 今天精析的这一篇综述,于2022-01-07发表于Science,主要讨论了癌症中的三级淋巴结构(Tertiary Lymphoid Structures, TLS)及其在肿瘤免疫反应中的作用。 作者类型作者姓名单位名称(中文)通讯作者介绍第一作者Ton N. Schumacher荷兰癌症研究所通讯作者之一通讯作者Daniela S. Thomm

08 增删查功能

划重点: lable 标签keyup:键盘事件标签内添加样式:style使用事件修饰符:preventforEach :遍历 数组indexOf: 可以返回要查询的某个字符串值在整个字符串中首次出现的位置下标findIndex:返回传入一个测试条件(函数)符合条件数组的首个元素的位置splice:向/从数组中添加/删除项目,然后返回被删除后的新的项目数组 黑椒蟹 一对: <!DOCTYPE

2021-08-14 react笔记-1 安装、环境搭建、创建项目

1、环境 1、安装nodejs 2.安装react脚手架工具 //  cnpm install -g create-react-app 全局安装 2、创建项目 create-react-app [项目名称] 3、运行项目 npm strat  //cd到项目文件夹    进入这个页面  代表运行成功  4、打包 npm run build

GUI编程08:画笔paint

本节内容视频链接:10、画笔paint_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1DJ411B75F?p=10&vd_source=b5775c3a4ea16a5306db9c7c1c1486b5 package com.yundait.lesson03;import java.awt.*;import java.awt.event.Wind

2025届计算机毕业设计:如何构建Java SpringBoot+Vue个人健康档案管理系统?

✍✍计算机编程指导师 ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java实战 | SpringBoot/SSM Python实战项目 | Django 微信小程序/安卓实战项目 大数据实战项目 ⚡⚡文末获取源码 文章目录