长乐培训Day3
2019-08-16 07:53:18来源：博客园 阅读 ()
长乐培训Day3
T1 奶牛晒衣服
题目
【题目描述】
在熊大妈英明的带领下，时针和他的同伴生下了许多牛宝宝。熊大妈决定给每个宝宝都穿上可爱的婴儿装。于是，为牛宝宝洗晒衣服就成了很不爽的事情。
圣人王担负起了这个重任。洗完衣服后，你就要弄干衣服。衣服在自然条件下用1的时间可以晒干A点湿度。抠门的熊大妈买了1台烘衣机。
使用烘衣机可以让你用1的时间使1件衣服除开自然晒干的A点湿度外，还可烘干B点湿度，但在1的时间内只能对1件衣服使用。
N件的衣服因为种种原因而不一样湿，现在告诉你每件衣服的湿度，要你求出弄干所有衣服的最少时间（湿度为0为干）。
【输入格式】
第一行N，A，B，接下来N行，每行一个数，表示衣服的湿度。
【输出格式】
一行，最少时间。
【输入样例】
3 2 1
1
2
3
【输出样例】
1
【数据规模】
1<=湿度,A,B<=500000,1<=N<=500000。
解析
第一题依旧是送分的（安慰一下其他题爆零的情绪QAQ）。
直接二分即可，每次循环中只需要判断s[i]（湿度）与a*mid（mid为天数）的大小就可以了。
最后的答案即为l。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } int n,a,b,s[500100]; long long l,r,mid; bool cmp(int x,int y) { return x>y; } int main() { //freopen("dry.in","r",stdin); //freopen("dry.out","w",stdout); n=read(),a=read(),b=read(); for(int i=1;i<=n;i++) { s[i]+=read(); r+=s[i]; } while(l<=r) { long long ans=0; mid=(l+r)>>1; for(int i=1;i<=n;i++) if(s[i]-a*mid>0) { if((s[i]-a*mid)%b==0) ans+=(s[i]-a*mid)/b; else ans+=(s[i]-a*mid)/b+1; } if(ans<=mid) r=mid-1; else l=mid+1; } cout<<l; return 0; //fclose(stdin); //fclose(stdout); }View Code
T2 解密文件
题目
【题目描述】
已知英语中26个字母出现的概率p[0],p[1]……,p[25]（它们的和为1），分别表示’a’, ‘b’,‘c’……出现的概率（大写字母和小写字母被认为是一样的）。
现在有一个加密过的文件，加密方法是将原文件中的每一个字母进行相同的变换，其他的字符不变，变换的方法如下：
如果将a到z编号为0到25，那么字母i将被替换成(i+k) mod 26，0<=k<26。原来是大写的字母，仍然是大写，原来是小写的字母仍然是小写。
但是你并不知道k的值，所以只好枚举。因为知道26个字母出现的频率，所以你可以选择一个尽量好的k，使得频率的方差和最小，方差和定义如下：
假设你枚举的k还原出来的原文件中的26个字母出现的概率为x[0], x[1], ……, x[25]，那么方差和为：(p[0]-x[0])^2 + (p[1]-x[1])^2 + …… + (p[25]-x[25])^2。
如果有两个相同的k一样好，那么选较小的k。
最后输出解密出的原文件。
【输入格式】
前26行分别是26个字母出现的概率。
接下来是一个只含有26个大小写字母和空格，换行符，标点符号，阿拉伯数字等的文本。
【输出格式】
解密过的文本。
【输入样例】
0.109375
0.000000
0.062500
0.015625
0.109375
0.015625
0.015625
0.000000
0.062500
0.015625
0.000000
0.078125
0.062500
0.062500
0.093750
0.015625
0.015625
0.031250
0.046875
0.046875
0.046875
0.000000
0.000000
0.000000
0.093750
0.000000
L dp Ol Bxtldq, ru brx fdq fdoo ph VsdfhIobhu.
L dp jodg wr vhh brx.
Hqmrb pb frqwhvw.
【输出样例】
I am Li Yuqian, or you can call me SpaceFlyer.
I am glad to see you.
Enjoy my contest.
【数据规模】
输入文件不超过10k。
解析
这题直接模拟即可，非常恶心有趣。
先预处理出a数组（每个数字所对应的字母，0-25表示a-z，26-51表示A-Z）。
处理文本我用的是string，直接while循环getline(cin,s[++temp])，这里有两个细节：
1、输入时要先输入一个“\n”（我也不知道为什么，反正它会读入一个换行）；
2、由于++temp，所以即使没有读入了还是会自加一次，所以要-1或者输出时把<=改成<。
关于每个字母的频率，本蒟蒻是在枚举k时每次都计算，实际上并不用那么麻烦，
因为每个字母都是由初始字母一一对应转换来的，所以只需要计算初始字母的频率就行了（输入时明明给了的说）。
然后取方差和最小的即可。输出时如果是字母要分大写和小写处理，
小写输出a[(int)((s[i][j]-'a'+kk)%26)]，大写输出a[(int)((s[i][j]-'A'+kk)%26+26)]（预处理a数组是大写字母实在小写字母基础上+26的）。
如果不是字母直接输出原来的文本就好了。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int temp=0,sum[55],kk; double p[26],x[26],ans,minn=1000000.0; char a[55]; string s[10001]; int main() { //freopen("decode.in","r",stdin); //freopen("decode.out","w",stdout); for(int i=0;i<26;i++) a[i]=char('a'+i); for(int i=26;i<52;i++) a[i]=char('A'+i-26); for(int i=0;i<26;i++) cin>>p[i]; scanf("\n"); while(getline(cin,s[++temp])) ; for(int k=0;k<26;k++) { memset(sum,0,sizeof(sum)); ans=0.0; for(int i=1;i<=temp;i++) for(int j=0;j<s[i].size();j++) { if(s[i][j]>='a'&&s[i][j]<='z') sum[(s[i][j]-'a'+k)%26]++; if(s[i][j]>='A'&&s[i][j]<='Z') sum[(s[i][j]-'A'+k)%26]++; } for(int i=0;i<26;i++) { x[i]=(double)(sum[i]*0.03846153846); ans+=(p[i]-x[i])*(p[i]-x[i]); } if(ans<minn) { minn=ans; kk=k; } } for(int i=1;i<temp;i++) { for(int j=0;j<s[i].size();j++) { if(s[i][j]>='a'&&s[i][j]<='z') cout<<a[(int)((s[i][j]-'a'+kk)%26)]; else if(s[i][j]>='A'&&s[i][j]<='Z') cout<<a[(int)((s[i][j]-'A'+kk)%26+26)]; else cout<<s[i][j]; } cout<<endl; } return 0; //fclose(stdin); //fclose(stdout); }View Code
T3 休息
题目
【题目描述】
休息的时候，可以放松放松浑身的肌肉，打扫打扫卫生，感觉很舒服。在某一天，某LMZ开始整理他那书架。
已知他的书有n本，从左到右按顺序排列。他想把书从矮到高排好序，而每一本书都有一个独一无二的高度Hi。
他排序的方法是：每一次将所有的书划分为尽量少的连续部分，使得每一部分的书的高度都是单调下降，然后将其中所有不少于2本书的区间全部翻转。
重复执行以上操作，最后使得书的高度全部单调上升。可是毕竟是休息时间，LMZ不想花太多时间在给书排序这种事上面。
因此他划分并翻转完第一次书之后，他想计算，他一共执行了多少次翻转操作才能把所有的书排好序。
LMZ惊奇地发现，第一次排序之前，他第一次划分出来的所有区间的长度都是偶数。
【输入格式】
第一行一个正整数n, 为书的总数。
接下来n行，每行仅一个正整数Hi，为第i本书的高度。
【输出格式】
仅一个整数，为LMZ需要做的翻转操作的次数。
【输入样例】
6
5 3 2 1 6 4
【输出样例】
3
【数据规模】
对于10%的数据：n<=50
对于40%的数据：n<=3000
对于100%的数据：1<=n<=100000, 1<=Hi<=n
解析
其实这题就是在求逆序对，所以用归并排序来做。
在归并的过程中，如果a[i]>a[j]，即逆序对，则ans+=mid-i+1，具体原因模拟一遍就知道了。
程序中运用到的reverse函数是<algorithm>里的，作用是翻转，在给p[cnt].r赋值的时候,赋的是i-1，所以在翻转时，得在最后+1。
答案是在n2/2的，很显然int是不够的，记得开long long。
Code
#include<algorithm> #include<iostream> #include<cstdio> using namespace std; const int N = 1e5 + 10; int c[N], a[N], n; long long ans; void msort(int l, int r) { if(l == r) return; int mid = (l + r) >> 1; msort(l, mid), msort(mid + 1, r); int i = l, j = mid + 1, k = l; while(i <= mid && j <= r) { if(a[i] <= a[j]) c[k++] = a[i++]; else { ans += mid - i + 1; c[k++] = a[j++]; } } while(i <= mid) c[k++] = a[i++]; while(j <= r) c[k++] = a[j++]; for(int t = l; t <= r; t++) a[t] = c[t]; } struct rec { int l, r; }p[N]; int main() { //freopen("rest.in", "r", stdin); //freopen("rest.out", "w", stdout); int cnt = 0; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", a + i); if(a[i] > a[i - 1]) { p[cnt].r = i - 1; p[++cnt].l = i; } } p[cnt].r = n; for(int i = 1; i <= cnt; i++) reverse(a + p[i].l, a + p[i].r + 1), ans++; msort(1, n); cout<<ans; return 0; }View Code
T4 矩阵取数游戏
题目
【题目描述】
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：
1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有的元素；
2.每次取走的各个元素只能是该元素所在行的行首或行尾；
3.每次取数都一个得分值，为每行取数的得分之和；每行取数的得分=被取走的元素值*2i，其中i表示第i次取数(从1开始编号)；
4.游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
【输入格式】
输入文件包括n+1行：
第一行为两个用空格隔开的整数n和m。
第2~n+1行为n*m矩阵，其中每行m个用单个空格隔开。
【输出格式】
输出文件仅包含1行，为一个整数，即输入矩阵取数后的最大的分。
【输入样例】
2 3
1 2 3
3 4 2
【输出样例】
82
【数据规模】
60%的数据满足：1<=n, m<=30，答案不超过1016
100%的数据满足：1<=n, m<=80，0<=aij<=1000
解析
这题实际上一眼就可以看出是区间DP。
令f[i][j]表示第k行取数取成了[i,j]的区间的得分。
由于只能从左右两端取，所以状态转移方程显而易见：
f[i][j]=max(f[i-1][j]+a[i-1][j]*2m-j+i-1,f[i][j+1]+a[i][j+1]*2m-j+i-1)
由于本蒟蒻的代码i和j都是从0开始循环的所以2的次方并不是m-j+i-1，而是i+j（个人更推荐上面的写法，更通俗易懂）。
好了，这题就是这样。
才怪，
如果单单只是这样的话，这题就太简单了，
但是！！！！！
注意看数据范围，m最大为80，那么2的80次方是多少？1208925819614629174706176！
这么大的数int不行，long long也不行，哪怕是unsigned long long也不够，那怎么办呢？
答案是：高精！
高精才是这道题真正恶心的地方，需要用到的有：
高精+高精、高精*单精、max(高精,高精)。
所以本蒟蒻来讲一下高精如何实现......才怪。
由于本蒟蒻不会高精，所以下面代码中的高精是直接从标程“借鉴”来的（手动滑稽）。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } int n,m,a[85][85]; struct sb{ int c[16]; friend inline sb operator * (const sb &a, const int &b) { sb c; for(int i = 1; i <= 15; i ++) c.c[i] = 0; c.c[0] = a.c[0]; int p = 0; for(int i = 1; i <= a.c[0]; i ++) { c.c[i] = a.c[i] * b + p; p = c.c[i] / 10000; c.c[i] %= 10000; } int &len = c.c[0]; while (p) { c.c[++len] = p % 10000; p /= 10000; } return c; } friend inline sb operator * (const sb &a, const sb &b) { sb c; for(int i = 1; i <= 15; i ++) c.c[i] = 0; c.c[0] = a.c[0] + b.c[0] - 1; for(int i = 1; i <= a.c[0]; i ++) { int p = 0; for(int j = 1; j <= b.c[0]; j ++) { c.c[i + j - 1] += a.c[i] * b.c[j] + p; p = c.c[i + j - 1] / 10000; c.c[i + j - 1] %= 10000; } c.c[i + b.c[0]] += p; } if (c.c[c.c[0] + 1]) c.c[0] ++; return c; } friend inline sb operator + (const sb &a, const sb &b) { sb c; int &len = c.c[0]; c.c[0] = max(a.c[0], b.c[0]); for(int i = 1; i <= 15; i ++) c.c[i] = 0; int p = 0; for(int i = 1; i <= len; i ++) { c.c[i] = a.c[i] + b.c[i] + p; p = c.c[i] / 10000; c.c[i] %= 10000; } if (p) len ++, c.c[len] = p; return c; } inline sb operator = (const sb &b) { c[0] = b.c[0]; for(int i = 1; i <= 15; i ++) c[i] = 0; for(int i = 1; i <= b.c[0]; i ++) c[i] = b.c[i]; return *this; } inline void print() { cout << c[c[0]]; for(int i = c[0] - 1; i >= 1; i --) printf("%04d", c[i]); cout << endl; } }; inline sb Max(const sb &a, const sb &b) { if (a.c[0] > b.c[0]) return a; else if (a.c[0] < b.c[0]) return b; else if (a.c[0] == b.c[0]) { for(int i = a.c[0]; i >= 1; i --) if (a.c[i] > b.c[i]) return a; else if (a.c[i] < b.c[i]) return b; } return a; } sb f[85][85],cf[85],tot,ans; int main() { //freopen("game.in","r",stdin); //freopen("game.out","w",stdout); n=read(),m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(); cf[0].c[0]=1;cf[0].c[1]=1; for(int i=1;i<=m;i++) cf[i]=cf[i-1]*2; for(int k=1;k<=n;k++) { for(int i=0;i<=m;i++) for(int j=0;j<=m;j++) memset(f[i][j].c,0,sizeof(f[i][j].c)); f[m][m].c[0]=1; memset(tot.c,0,sizeof(tot.c)); tot.c[0]=1; for(int i=0;i<=m;i++) for(int j=0;j<=m-i;j++) { if(i==0&&j==0) continue; if(i) f[i][j]=Max(f[i][j],f[i-1][j]+cf[i+j]*a[k][i]); if(j) f[i][j]=Max(f[i][j],f[i][j-1]+cf[i+j]*a[k][m-j+1]); tot=Max(tot,f[i][j]); } ans=ans+tot; } ans.print(); //fclose(stdin); //fclose(stdout); return 0; }View Code
原文链接:https://www.cnblogs.com/I-Love-You-520/p/11239720.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
下一篇：中国剩余定理
- 清北学堂day3 2019-11-04
- 长乐国庆集训Day1 2019-10-08
- 长乐国庆集训Day4 2019-10-08
- 长乐国庆集训Day5-2 2019-10-08
- 长乐国庆集训Day3 2019-10-08
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
