嫣然一笑II

【问题描述】（模拟）
一张长度为N的纸带，我们可以从左至右编号为0 − N（纸带最左端 标号为
0） 。 现在有M次操作， 每次将纸带沿着某个位置进行折叠， 问所有操作之后纸带
的长度是多少。
【输入格式】
第一行两个数字N,M如题意所述。
接下来一行M个整数代表每次折叠的位置。
【输出格式】
一行一个整数代表答案。
【样例输入】
5 2
3 5
【样例输出】
2
【样例解释】
树上有只鸟。
【数据规模与约定】
对于60%的数据，N,M ≤ 3000。
对于100%的数据，N≤ 10^18, M≤ 3000。

题解：

#include<iostream> #include<cstdio> using namespace std; long long a[50005]; int main() {long long n,m;scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++){scanf("%lld",&a[i]);}long long r=n;for(int i=1;i<=m;i++){for(int j=i+1;j<=m;j++){if(a[j]<=a[i]){a[j]=a[i]+a[i]-a[j];}}r=max(a[i]+a[i],r);for(int j=i+1;j<=m;j++){a[j]-=a[i];}r-=a[i];}printf("%lld",r);return 0; }

————————————————–我是华丽的分割线—————————————————–

无向图找环

Description
给你一副无向图，每条边有边权，保证图联通，现在让你判断这个图是否满足任意一个环的边权异或和为0。

Input

多组测试数据，先输入一个数字T，T组每组先输入两个数n m，表示图的点跟边的数量。

然后是m行，每行三个数a b c。代表一条边的起点，终点，边权。

Input
多组测试数据，每组先输入两个数n m，表示图的点跟边的数量。

然后是m行，每行三个数a b c。代表一条边的起点，终点，边权。

1 <= n<= 100, 1 <= m <= 100.

1 <= a <= n, 1 <= b <= n, a != b.

0 <= c <= 2^16-1

Output
对于每组数据输出Yes或者 No（若满足输出Yes,不存在输出No）。

Sample Input
3 3
1 2 0
2 3 1
3 1 1

Sample Output
Yes

题解（dfs）：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=505; struct cc{int from,to,cost; }es[maxn]; int first[maxn],next[maxn]; int tot=0; void build(int ff,int tt,int pp) { es[++tot]=(cc){ff,tt,pp}; next[tot]=first[ff]; first[ff]=tot; } int vis[maxn]; int dis[maxn]; bool flag; void dfs(int x) {for(int i=first[x];i;i=next[i]){int u=es[i].to;if(!vis[u]){vis[u]=1;dis[u]=dis[x]^es[i].cost;dfs(u);}else {if((dis[x]^dis[u]^es[i].cost )!=0){flag=1;return ;}}} } void init() {memset(dis,0,sizeof(0));memset(vis,0,sizeof(vis));memset(es,0,sizeof(es));memset(first,0,sizeof(first));memset(next,0,sizeof(next));flag=0; } int main() {int T;scanf("%d",&T);while(T--){init();int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);build(x,y,z);build(y,x,z);}for(int i=1;i<=n;i++){if(!vis[i]){vis[i]=1;dfs(i); }}if(flag){printf("No\n"); }else{printf("Yes\n"); }} return 0; }

——————————————————我是华丽的分割线——————————————————

完美的序列(sequence)
Time Limit:1000ms Memory Limit:64MB
题目描述
LYK 认为一个完美的序列要满足这样的条件：对于任意两个位置上的数都不相同。然而
并不是所有的序列都满足这样的条件。
于是 LYK 想将序列上的每一个元素都增加一些数字(当然也可以选择不增加)，使得整个
序列变成美妙的序列。
具体地， LYK 可以花费 1 点代价将第 i 个位置上的数增加 1，现在 LYK 想花费最小的代价
使得将这个序列变成完美的序列。
输入格式(sequence.in)
第一行一个数 n，表示数字个数。
接下来一行 n 个数 ai 表示 LYK 得到的序列。
输出格式(sequence.out)
一个数表示变成完美的序列的最小代价。
输入样例
4
1 1 3 2
输出样例
3
数据范围
对于 30%的数据 n<=5。
对于 60%的数据 n<=1000。
对于 80%的数据 n<=30000，ai<=3000。
对于 100%的数据 n<=100000，1<=ai<=100000。

题解（排序？！）：

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int a[300005]; int main() {int n;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);a[x]++;}int ans=0;for(int i=1;i<=300000;i++){if(a[i]>1){ans+=a[i]-1;a[i+1]+=a[i]-1;}}printf("%d",ans);return 0; }

—————————————————我是华丽的分割线——————————————————-

LYK 与实验室(lab)
Time Limit:5000ms Memory Limit:64MB
题目描述
LYK 在一幢大楼里，这幢大楼共有 n 层，LYK 初始时在第 a 层上。
这幢大楼有一个秘密实验室，在第 b 层，这个实验室非常特别，对 LYK 具有约束作用，
即若 LYK 当前处于 x 层，当它下一步想到达 y 层时，必须满足|x-y|<|x-b|，而且由于实验室
是不对外开放的，电梯无法停留在第 b 层。
LYK 想做一次旅行，即它想按 k 次电梯，它想知道不同的旅行方案个数有多少个。
两个旅行方案不同当前仅当存在某一次按下电梯后停留的楼层不同。
输入格式(lab.in)
一行 4 个数，n,a,b,k。
输出格式(lab.out)
一个数表示答案，由于答案较大，将答案对 1000000007 取模后输出。
输入样例 1
5 2 4 1
输出样例 1
2
输入样例 2
5 2 4 2
输出样例 2
2
输入样例 3
5 3 4 1
输出样例 3
0
数据范围
对于 20%的数据 n,k<=5。
对于 40%的数据 n,k<=10。
对于 60%的数据 n,k<=500。
对于 90%的数据 n,k<=2000。
对于 100%的数据 n,k<=5000。

题解（dp）：

#include<iostream> #include<cstdio> using namespace std; const int mod=1000000007; long long dp[5005],sum[5005]; int main() { int n,a,b,k;qscanf("%d%d%d%d",&n,&a,&b,&k); dp[a]=sum[a]=1;int ans=0;for(int i=a+1;i<=n;i++){sum[i]=1;//前缀和 }for(int i=1;i<=k;i++){for(int j=1;j<=n;j++){if(j<b)//实验室下半部分到不了实验室上方 {dp[j]=(sum[(j+b-1)/2]-sum[j]+sum[j-1]+mod)%mod;}if(j>b)//实验室上半部分到不了实验室下方 {dp[j]=(sum[n]-sum[(j+b)/2]+mod-sum[j]+sum[j-1]+mod)%mod; }if(j==b){dp[j]=0;//实验室不能到达}}for(int j=1;j<=n;j++){sum[j]=(sum[j-1]+dp[j])%mod;//前缀和 }}for(int i=1;i<=n;i++){ans=(ans+dp[i])%mod;//统计 }printf("%d",ans);return 0; }

转载于:https://www.cnblogs.com/-feather/p/7779901.html

总结

以上是生活随笔为你收集整理的嫣然一笑II的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。