BUPT2014新生暑假个人排位赛07

2024-08-24 12:18
文章标签 个人 暑假 07 新生 排位赛 bupt2014

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

BOJ 469 暑假作业题

纯模拟，细心耐心，这是我觉得姿势最丑的一次代码 
#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>using 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;ll num;
ll E,W,Q,B,S,n;bool sovleW(ll n,int have3)//传入 w 之内的数
{if(n==0)return false;int temp=n/1000LL;int have=0,have2=0;if(temp>0){printf("%dQ",temp);have=1;have3=0;}n%=1000LL;temp=n/100LL;if(temp>0){if(have3)putchar('0');printf("%dB",temp);have=0;have2=1;have3=0;}n%=100LL;temp=n/10LL;if(temp>0){if(have||have3)putchar('0');have=0;have2=0;have3=0;printf("%dS",temp);}n%=10LL;temp=n;if(temp>0){if(have||have2||have3)putchar('0');printf("%d",temp);}
}bool sovleE(ll n)
{if(n==0)return false;int temp=n/100000000LL;int have=0,have2=0;if(temp>0){printf("%dE",temp);have=1;}n%=100000000LL;temp=n/10000LL;if(temp>0){sovleW(temp,have);putchar('W');have2=1;}n%=10000LL;sovleW(n,have2||have);
}int main()
{int T;
//    freopen("data.txt","r",stdin);read(T);while(T--){read(n);E=n/100000000LL;int have=0,have2=0;if(E>0){sovleE(E);putchar('E');have=1;}n%=100000000LL;W=n/10000;if(W>0){sovleW(W,have);putchar('W');have2=1;}n%=10000;if(n>0){sovleW(n,have2||have);}if(n==0&&!have&&!have2)putchar('0');putchar('\n');}return 0;
}

BOJ 443 最长数链

原意是考察DFS，但是人工总结出了最优解，
第二项为 2 或者 3，其余项为前一项乘 2 。明显地，前一项乘 2 将会构成最长的数列，如果第二项是4的话，肯定比第二项为2的短，其余更大的数类推。
至于 2 和 3 ，则根据所给数关于 2 的 幂的关系 
#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>using 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;
}//-----------------------------------------------------------------------int main()
{int n;while(read(n)){int temp=(log(n/1.0)/log(2.0)+1e-9);int a=log((double)n/2.0)/log(2.0);int b=log((double)n/3.0)/log(2.0);
//       cout<<a<<" "<<b<<endl;cout<<" "<<temp<<" "<<log(n/1.0)/log(2.0)<<endl;if(a!=b||fabs((double)temp-log(n/1.0)/log(2.0))<=1e-9){putchar('1');for(int i=2;i<=n;i*=2)printf(" %d",i);putchar('\n');}else if(a==b){putchar('1');for(int i=3;i<=n;i*=2)printf(" %d",i);putchar('\n');}}return 0;
}

BOJ 453 三角形的传说

数学题，可以用找规律代替计算。
详见代码，大尧神总结出了一个规范的证明，过段时间再贴上来吧 
#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 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);
}//-----------------------------------------------------------------------int m,q;int main()
{int T,cas=0;for(read(T);cas<T;){read(m),read(q);printf("Case %d: ",++cas);int circle=2*q;if(q*2>m){write(circle+m);}else if(q!=1&&q!=0){write(circle+2*m);}else{write(circle+3*m);}putchar('\n');}return 0;
}

BOJ 454 帮帮小叮当

图论之最短路
构图方法：
将所有的传送站与（1,1）点、（n,m）点相连，权值为 两点的曼哈顿距离，所有相邻行的传送站相连，权值为1、
用姿势好的spfa，或者spfa+slf优化，或者更加松弛方向优化
根据松弛方向优化（应该是贪心决策了必然的松弛方向，然后进行类似DP的递推） 

#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=10010;
int n,m;
struct Node
{int diss,dise;int x,y;
}c[MAXN];
int dp[MAXN];int dist(int x,int y,int xx,int yy)
{return fabs(x-xx)+fabs(y-yy);
}//  相邻行的传送门int main()
{//   freopen("data.txt","r",stdin);while(read(n)&&read(m)&&n&&m){for(int i=1;i<=n;i++){read(c[i].y);c[i].x=i;c[i].diss=dist(c[i].x,c[i].y,1,1);c[i].dise=dist(c[i].x,c[i].y,n,m);}dp[0]=INF;for(int i=1;i<=n;i++)dp[i]=min(dp[i-1]+1,c[i].diss);for(int i=n-1;i>=1;i--)dp[i]=min(dp[i+1]+1,dp[i]);int ans=INF;for(int i=1;i<=n;i++)ans=min(ans,dp[i]+c[i].dise);printf("%d\n",ans);}return 0;
}

姿势稍微好一些的SPFA，代码由大A神提供 
#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;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;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;
int n,m,Index;
int head[MAXN],next[5*MAXN],node[5*MAXN],value[5*MAXN],path[MAXN],cnt[MAXN];
bool vis[MAXN];
struct cmp
{bool operator ()(const int &a,const int &b) const{return  path[a]<path[b] || (path[a]==path[b] && a<b);}
};
void addnode(int a,int b,int v)
{Index++;next[Index]=head[a];node[Index]=b;value[Index]=v;head[a]=Index;
}
int relax(int u, int v, int c)
{if( path[v] > path[u] + c ){path[v] = path[u] + c;return 1;}return 0;
}
int SPFA(int src, int n)
{// 此处用队列实现int i;memset(cnt, 0, sizeof(int)*(n+10)); // 入队次数memset(vis, false, sizeof(bool)*(n+10));for( i=1; i <= n; ++i ) path[i] = INF;path[src] = 0;queue<int> Q;Q.push(src); vis[src] = true; ++cnt[src];while( !Q.empty() ){int u, v;u = Q.front();Q.pop();vis[u] = false;for( i=head[u];i; i=next[i] ){v = node[i];if( 1 == relax(u, v, value[i]) && !vis[v] ){Q.push(v); vis[v] = true;if( (++cnt[v]) > n ) return -1; // cnt[i]为入队列次数，用来判断是否存在负权回路}}}if( path[n] == INF )return -2; // src与n不可达，有些题目可省！！！return path[n]; // 返回src到n的最短距离，根据题意不同而改变
}
int main()
{while(read(n)&&read(m)&&n&&m){Index=0;memset(head,0,sizeof(int)*(n+10));memset(next,0,sizeof(int)*(n+10));int temp;scanf("%d",&temp);addnode(0,1,temp-1);addnode(1,n+1,n-1+m-temp);for(int i=2;i<=n;i++){read(temp);addnode(i-1,i,1);addnode(i,i-1,1);addnode(0,i,i-1+temp-1);addnode(i,n+1,n-i+m-temp);}printf("%d\n",SPFA(0,n+1));}return 0;
}

用SLF优化的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 eps 1e-9
#define INF 0x3f3f3f3fusing namespace std;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;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;
int n,m,Index;
struct Edge
{int to,next,v;
}el[MAXN*5];
int head[MAXN],d[MAXN];
bool vis[MAXN];void addedge(int a,int b,int v)
{Index++;el[Index].next=head[a];el[Index].to=b;el[Index].v=v;head[a]=Index;
}void Spfa()
{memset(vis, false, sizeof(bool)*(n+10));d[0]=0;vis[0]=true;deque <int> q;q.push_back(0);while(!q.empty()){int x=q.front();q.pop_front();for(int k=head[x];k!=-1;k=el[k].next){int y=el[k].to;if(d[y]>d[x]+el[k].v){d[y]=d[x]+el[k].v;if(!vis[y]){vis[y]=true;if(!q.empty()){if(d[y]>d[q.front()])q.push_back(y);elseq.push_front(y);}elseq.push_back(y);}}}vis[x]=false;}return ;
}int main()
{while(read(n)&&read(m)&&n&&m){Index=0;memset(head,-1,sizeof(int)*(n+10));memset(d,0x3f,sizeof(int)*(n+10));int temp;read(temp);addedge(0,1,temp-1);addedge(1,n+1,n-1+m-temp);for(int i=2;i<=n;i++){read(temp);addedge(i-1,i,1);addedge(i,i-1,1);addedge(0,i,i-1+temp-1);addedge(i,n+1,n-i+m-temp);}Spfa();printf("%d\n",d[n+1]);}return 0;
}


BOJ 446 大神题

用线段树维护几个数之间的gcd（田神说gcd是加性函数
然后用记忆话搜索的容斥原理，计算出答案
容斥原理类似于   m/2+m/3-m/6 

#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 MAXN 10005
#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);
}ll prime[]={2,3,5,7,11,13,17,19,23,29,31};
struct node
{int left, right;ll gcd;
}arr[MAXN*6];ll num[MAXN], a[MAXN], c;
ll gcd(ll a, ll b)
{return b==0?a:gcd(b,a%b);
}
void build(int idx, int l, int r)
{arr[idx].left = l, arr[idx].right = r;arr[idx].gcd = 0;if(l == r){arr[idx].gcd = num[l];return;}int mid = (l + r) >> 1;build(idx << 1, l, mid);build(idx << 1 | 1, mid + 1, r);arr[idx].gcd = gcd(arr[idx << 1].gcd , arr[idx << 1 | 1].gcd);
}
ll ans;
bool query(int idx, int l, int r)
{if(arr[idx].right < l||arr[idx].left > r)return false;if(arr[idx].left >= l&&arr[idx].right <= r){ans=gcd(ans,arr[idx].gcd);return true;}query(idx << 1, l, r);query(idx << 1 | 1, l, r);return true;
}void update(int idx, int val, int pos)
{int l = arr[idx].left, r = arr[idx].right;if(l == r){arr[idx].gcd=val;return;}int mid = (l + r) >> 1;if(pos <= mid)update(idx << 1, val, pos);elseupdate(idx << 1 | 1, val, pos);//printf("%I64d(I64d,%I64d)\n",arr[idx].gcd, arr[idx<<1].gcd, arr[idx<<1|1].gcd);arr[idx].gcd = gcd(arr[idx<<1].gcd, arr[idx<<1|1].gcd);
}int fa[1010][10];
inline void Get_fac(int m)  
{  int tot=0,temp=m; if(fa[m][0]!=0)return;for(int i=2;i*i<=temp;i++)  if(temp%i==0){  fa[m][++tot]=i;  while(temp%i==0)temp/=i;  }  if(temp!=1)fa[m][++tot]=temp;  fa[m][0]=tot;  
}  int sum[1<<11],q;
ll Sum(int m,ll n)
{int i,j;Get_fac(m);sum[0]=1;sum[1]=1;for(i=1;i<=fa[m][0];i++){int k=sum[0];for(j=1;j<=sum[0];j++){sum[++k]=fa[m][i]*sum[j]*-1;}sum[0]=k;}
//	for(i=1;i<=sum[0];i++)	printf("%d ",sum[i]);printf("\n");ll ret=n;for(i=2;i<=sum[0];i++)ret+=n/sum[i];return ret;
}int main()
{int t, n, q, l, r, m;ll g1;//int c=floor(log(2)/log(2)+eps);while(read(n)){read(m);read(q);for(int i=1;i<=n;i++)read(num[i]);build(1,1,n);
/*        for(int i=1;i<2*n;i++)printf("(%d:%I64d[%d,%d]) ",i,arr[i].gcd,arr[i].left,arr[i].right);puts("");*/int cnt=floor(log(n)/log(2)+eps);int o;while(q--){read(o),read(l);if(o==1){read(r);ans=num[l];query(1,l,r);if(ans==1){write(-1);putchar('\n');}else{write(Sum(ans,m)-1);putchar('\n');}}else{read(g1); num[l]=g1;update(1,g1,l);}}}return 0;
}



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


http://www.chinasem.cn/article/1102454。

相关文章

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

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

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

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

分布式系统：分的微小服务，以小而独立的业务为单位，形成子系统。 然后分布式系统中需要有统一的调用，形成大的聚合服务。 同时，微服务群，需要有交流（通讯，注册中心，同步，异步），有管理（监控，调度）。 对外服务，需要有控制的对外开发，安全网关。
阅读更多...
Java IO 操作——个人理解

Java IO 操作——个人理解

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

LeetCode 第414场周赛个人题解

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

07 v-if和v-show使用和区别

划重点： v-ifv-show 小葱拌豆腐 <!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta http-equiv="X-UA-Compatible" content="
阅读更多...
2025届计算机毕业设计：如何构建Java SpringBoot+Vue个人健康档案管理系统？

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

✍✍计算机编程指导师 ⭐⭐个人介绍：自己非常喜欢研究技术问题！专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目：有源码或者技术上的问题欢迎在评论区一起讨论交流！ ⚡⚡ Java实战 | SpringBoot/SSM Python实战项目 | Django 微信小程序/安卓实战项目 大数据实战项目 ⚡⚡文末获取源码 文章目录
阅读更多...
[SWPUCTF 2021 新生赛]web方向(一到六题) 解题思路，实操解析，解题软件使用，解题方法教程

[SWPUCTF 2021 新生赛]web方向(一到六题) 解题思路，实操解析，解题软件使用，解题方法教程

题目来源 NSSCTF | 在线CTF平台因为热爱，所以长远！NSSCTF平台秉承着开放、自由、共享的精神，欢迎每一个CTFer使用。https://www.nssctf.cn/problem   [SWPUCTF 2021 新生赛]gift_F12 这个题目简单打开后是一个网页  我们一般按F12或者是右键查看源代码。接着我们点击ctrl+f后快速查找，根据题目给的格式我们搜索c
阅读更多...
【动手学深度学习】04 数据操作 + 数据预处理（个人向笔记）

【动手学深度学习】04 数据操作 + 数据预处理（个人向笔记）

数据操作 N维数组是机器学习和神经网络的主要数据结构其中 2-d 矩阵中每一行表示每一行表示一个样本 当维度来到三维的时候则可以表示成一张图片，再加一维就可以变成多张图片，再加一维则可以变成一个视频 访问元素 冒号表示从冒号左边的元素到冒号右边的前一个元素（开区间），其中如果左边为空，那么表示从第一个开始，如果右边为空，那么表示访问到最后一个，如果两边都为空，则表示全部访问其中一行中我们指
阅读更多...
java基础总结07-面向对象3(this关键字)

java基础总结07-面向对象3(this关键字)

this是一个引用，它指向自身的这个对象。 看内存分析图 假设我们在堆内存new了一个对象，在这个对象里面你想象着他有一个引用this，this指向这个对象自己，所以这就是this，这个new出来的对象名字是什么，我们不知道，不知道也没关系，因为这并不影响这个对象在内存里面的存在，这个对象只要在内存中存在，他就一定有一个引用this。 看下面的例子分析: package cn.ga
阅读更多...
【SpringMVC学习07】SpringMVC与前台的json数据交互

【SpringMVC学习07】SpringMVC与前台的json数据交互

json数据格式在接口调用中、html页面中比较常用，json格式比较简单，解析也比较方便，所以使用很普遍。在springmvc中，也支持对json数据的解析和转换，这篇文章主要总结一下springmvc中如何和前台交互json数据。 1. 两种交互形式 　springmvc和前台交互主要有两种形式，如下图所示： 可以看出，前台传过来的方式有两种，一种是传json格式的数据过来，另一种
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2