BUPT2014新生暑假个人排位赛09

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

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

475. 小妹妹快递公司的新址

BOJ 470 diffsum
一开始思路有问题，但是实在是没有成功构建出能够hack自己的数据
思路有两个
第一个是，峰神神奇的证明出了，答案是由数列从大到小排列后，以 n-1 为首项， 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>
#define eps 1e-9
#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;
}//-----------------------------------------------------------------------const int MAXN=100010;
int n,m;
int a[MAXN];int main()
{while(read(n)){ll temp=n-1;ll ans=0,fusum=0,zhsum=0;ll zhnum=0,funum=0;for(int i=0;i<n;i++)scanf("%lld",&a[i]);if(n==1){printf("0\n");continue;}sort(a,a+n);for(int i=n-1;i>=0;i--){ans+=temp*a[i];temp-=2;}printf("%lld\n",ans);}return 0;
}

第二个则是我的想法
将数列按照递增排序，改点的角标乘以改点的值减去改点的前缀和 
#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 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;
}//-----------------------------------------------------------------------const int MAXN=100010;ll a[MAXN];
ll sum[MAXN];
int main()
{int n, m, t;ll ans=0;while(read(n)){ans=0;for(int i=0;i<n;i++)read(a[i]);sort(a,a+n);sum[0]=a[0];for(int i=1;i<n;i++){sum[i]=sum[i-1]+a[i];ans=ans-sum[i-1]+a[i]*i;}printf("%lld\n",ans);}return 0;
}

BOJ 474 小妹妹送很多快递

最小生成树
在边权不为0的时候，答案加上（左边集合的元素个数）*（右边集合的元素个数）*（边权）
在边权为1的时候，将边权特判为1，继续上面操作 

#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 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;
}//-----------------------------------------------------------------------const int MAXN=10010;
const int MAXE=100010;struct Edge
{int u,v,w;
}e[MAXE];int n,m;
int fa[10010],rank[MAXN],sum[MAXN];
int tot;int find_fa(int x)
{if(fa[x]==x)return x;elsereturn fa[x]=find_fa(fa[x]);
}void Merge(int x,int y)
{if(rank[x]>rank[y]){fa[y]=x;sum[x]+=sum[y];}else{fa[x]=y;sum[y]+=sum[x];if(rank[x]==rank[y])rank[y]++;}
}bool cmp(Edge a,Edge b)
{return a.w<b.w;
}void Kruskal()
{sort(e+1,e+m+1,cmp);ll ans=0;for(int i=1;i<=m;i++){int xx=find_fa(e[i].u);int yy=find_fa(e[i].v);if(xx!=yy){tot--;if(!e[i].w)ans+=2*sum[xx]*sum[yy];elseans+=2*sum[xx]*sum[yy]*e[i].w;Merge(xx,yy);}}printf("%lld\n",ans);
}int main()
{int T;read(T);while(T--){read(n);read(m);memset(rank,0,sizeof(rank));tot=n;for(int i=1;i<=n;i++)fa[i]=i,sum[i]=1;for(int i=1;i<=m;i++){read(e[i].u);read(e[i].v);read(e[i].w);}Kruskal();}return 0;
}

BOJ 477 新来的小妹妹

模板题
维护后缀树
计算后缀树中最长重复子串的位置（即height数组） 

#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);
}//-----------------------------------------------------------------------const int MAXN=200000;void radix(int *str,int *a,int *b,int n,int m)
{static int count[200000];memset(count,0,sizeof(count));for(int i=0;i<n;++i)++count[str[a[i]]];for(int i=1;i<=m;++i)count[i]+=count[i-1];for(int i=n-1;i>=0;--i)b[--count[str[a[i]]]]=a[i];
}void suffix_array(int *str,int *sa,int n,int m)
{static int rank[200000],a[200000],b[200000];for(int i=0;i<n;i++)rank[i]=i;radix(str,rank,sa,n,m);rank[sa[0]]=0;for(int i=1;i<n;i++)rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);for(int i=0;1<<i <n;++i){for(int j=0;j<n;++j){a[j]=rank[j]+1;b[j]=j +(1<<i)>=n? 0:rank[j+(1<<i)] +1;sa[j]=j;}radix(b,sa,rank,n,n);radix(a,rank,sa,n,n);rank[sa[0]]=0;for(int j=1;j<n;j++){rank[sa[j]]=rank[sa[j-1]]+(a[sa[j-1]]!=a[sa[j]]||b[sa[j-1]]!=b[sa[j]]);}}
}string duplicate_substr(string str)
{string rev;static int s[3000],sa[3000],rank[3000],h[3000];int n=str.length();copy(str.begin(),str.end(),s);suffix_array(s,sa,n,256);for(int i=0;i<n;++i)rank[sa[i]]=i;int k=0;int ans1=0,pos1=0;for(int i=0;i<n;i++){k= k==0? 0:k-1;while(rank[i]>0&&s[i+k]==s[sa[rank[i]-1]+k])++k;h[rank[i]]=k;if(h[rank[i]]>ans1){ans1=h[rank[i]];pos1=i;}}return str.substr(pos1,ans1);
}int main()
{int T;read(T);while(T--){string s;cin>>s;s=duplicate_substr(s);printf("%d\n",s.length());}return 0;
}

BOJ 476 学妹去搬砖

最简单的轮廓线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-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;
}
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=11;
const int MOD=1000000007;int n,m,k;
ll dp[2][1<<MAXN];
int color[MAXN][MAXN];void DP()
{ll *crt=dp[0],*next=dp[1];crt[0]=1;for(int i=n-1;i>=0;i--){for(int j=m-1;j>=0;j--){for(int used=0;used< 1<<m;used++){if((used>>j & 1)||color[i][j])next[used]=crt[used & ~(1<<j)];else{ll res=0;if(j+1<m && !(used>>(j+1) & 1) && !color[i][j+1]){res+=crt[used | 1<<(j+1)];}if(i+1<n && !color[i+1][j]){res+=crt[used | 1<<j];}next[used]= res % MOD;}}swap(crt,next);}}printf("%lld\n",crt[0]);
}int main()
{while(read(n)&&read(m)&&read(k)){int x,y;memset(color,0,sizeof(color));memset(dp,0,sizeof(dp));for(int i=1;i<=k;i++){read(x);read(y);color[x][y]=1;}DP();}return 0;
}


BOJ 475 小妹妹快递公司的新址

先求出该树的重心，然后以重心为根重新计算子孙的个数
同时，更新dp[ i ][ j ] （表示以 i 为根，有 j 个节点的子树的个数）状态转移为 dp 【father】【num】 + = ( dp【father】【num - k 】* dp【child】【k】) 
计算出来以后就开始一个神奇的DP，DP的思路是birdsrom写的..... 
</pre></div><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-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;
}
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=222;
const int MOD=10007;struct Edge
{int to,next;
} e[MAXN*2];
int n,mi;
int head[MAXN],tot=0;
int son[MAXN],cen,pre[MAXN];
int dp[MAXN][MAXN],sum[MAXN],child[MAXN];
bool vis[MAXN];void add(int u,int v)
{e[tot].next=head[u];e[tot].to=v;head[u]=tot++;e[tot].next=head[v];e[tot].to=u;head[v]=tot++;
}int dfsson(int x)
{int y,mx=0;vis[x]=true;son[x]=1;for(int i=head[x];~i;i=e[i].next){y=e[i].to;if(vis[y])continue;int tm=dfsson(y);mx=max(tm,mx),son[x]+=tm;}mx=max(mx,n-son[x]);if (mx<mi){mi=mx,cen=x;}return son[x];
}int dfs(int x)
{dp[x][0]=dp[x][1]=1;child[x]=1;//cout<<x<<" "<<pre[x]<<endl;system("pause");for(int i=head[x];~i;i=e[i].next){int y=e[i].to;if(pre[y])continue;pre[y]=x;;child[x]+=dfs(y);}for(int i=head[x];~i;i=e[i].next){int y=e[i].to;if(pre[x]==y)continue;for(int i=child[x];i>=2;i--)for(int j=1;j<i&&j<=child[y];j++)dp[x][i]=(dp[x][i]+dp[y][j]*dp[x][i-j])%MOD;}return child[x];
}int main()
{int T;
//    freopen("data.txt","r",stdin);read(T);while(T--){memset(head,-1,sizeof(head));memset(dp,0,sizeof(dp));memset(pre,0,sizeof(pre));memset(vis,false,sizeof(vis));tot=0;read(n);mi=n;int u,v;for(int i=0; i<n-1; i++){read(u),read(v);add(u,v);}dfsson(1);pre[cen]=-1;dfs(cen);//cout<<cen<<endl;int ret=0,ans=0;for(int i=1;i<=n;i++)ans=(ans+dp[cen][i])%MOD;ret=ans;for(int k=head[cen];~k;k=e[k].next){for(int i=0;i<=n;i++)sum[i]=dp[cen][i];int y=e[k].to;for(int i=1;i<=n;i++)for(int j=1;j<i;j++)sum[i]=((sum[i]-sum[i-j]*dp[y][j])%MOD+MOD)%MOD;//下面是birdstorm的思路，我实在是写不下去了sum[0]=1;for(int i=1;i<n;i++)sum[i]=(sum[i-1]+sum[i+1])%MOD;for(int i=1;i<=n;i++)ret=((ret-dp[y][i]*sum[i-1])%MOD+MOD)%MOD;}printf("%d\n",(ans-ret+MOD)%MOD);}return 0;
}


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


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

相关文章

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

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

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

Java第二阶段---09类和对象---第三节 构造方法

第三节 构造方法 1.概念 构造方法是一种特殊的方法，主要用于创建对象以及完成对象的属性初始化操作。构造方法不能被对象调用。 2.语法 //[]中内容可有可无 访问修饰符 类名([参数列表]){ } 3.示例 public class Car {     //车特征(属性）     public String name;//车名   可以直接拿来用 说明它有初始值     pu
阅读更多...
分布式系统的个人理解小结

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

分布式系统：分的微小服务，以小而独立的业务为单位，形成子系统。 然后分布式系统中需要有统一的调用，形成大的聚合服务。 同时，微服务群，需要有交流（通讯，注册中心，同步，异步），有管理（监控，调度）。 对外服务，需要有控制的对外开发，安全网关。
阅读更多...
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. 将日期转换为二进制表示 思路分析
阅读更多...
Science｜癌症中三级淋巴结构的免疫调节作用与治疗潜力｜顶刊精析·24-09-08

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

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

09 生命周期

生命周期 beforeCreatecreatedbeforeMountmountedbeforeUpdateupdatedbeforeDestorydestoryed 辣子鸡：香辣入口，犹如吃了炫迈一样 - - - 根本停不下来 <!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><meta name="viewport"
阅读更多...
Learn ComputeShader 09 Night version lenses

Learn ComputeShader 09 Night version lenses

这次将要制作一个类似夜视仪的效果 第一步就是要降低图像的分辨率， 这只需要将id.xy除上一个数字然后再乘上这个数字 可以根据下图理解，很明显通过这个操作在多个像素显示了相同的颜色，并且很多像素颜色被丢失了，自然就会有降低分辨率的效果 效果： 但是这样图像太锐利了，我们加入噪声去解决这个问题 [numthreads(8, 8, 1)]void CSMain(uint3 id
阅读更多...
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
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2