t1 奶牛晒衣服
题目
【题目描述】
在熊大妈英明的带领下，时针和他的同伴生下了许多牛宝宝。熊大妈决定给每个宝宝都穿上可爱的婴儿装。于是，为牛宝宝洗晒衣服就成了很不爽的事情。
圣人王担负起了这个重任。洗完衣服后，你就要弄干衣服。衣服在自然条件下用1的时间可以晒干a点湿度。抠门的熊大妈买了1台烘衣机。
使用烘衣机可以让你用1的时间使1件衣服除开自然晒干的a点湿度外，还可烘干b点湿度，但在1的时间内只能对1件衣服使用。
n件的衣服因为种种原因而不一样湿，现在告诉你每件衣服的湿度，要你求出弄干所有衣服的最少时间（湿度为0为干）。
【输入格式】
第一行n，a，b，接下来n行，每行一个数，表示衣服的湿度。
【输出格式】
一行，最少时间。
【数据规模】
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); }
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个大小写字母和空格，换行符，标点符号，阿拉伯数字等的文本。
【输出格式】
解密过的文本。
【数据规模】
输入文件不超过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); }
t3 休息
题目
【题目描述】
休息的时候，可以放松放松浑身的肌肉，打扫打扫卫生，感觉很舒服。在某一天，某lmz开始整理他那书架。
已知他的书有n本，从左到右按顺序排列。他想把书从矮到高排好序，而每一本书都有一个独一无二的高度hi。
他排序的方法是：每一次将所有的书划分为尽量少的连续部分，使得每一部分的书的高度都是单调下降，然后将其中所有不少于2本书的区间全部翻转。
重复执行以上操作，最后使得书的高度全部单调上升。可是毕竟是休息时间，lmz不想花太多时间在给书排序这种事上面。
因此他划分并翻转完第一次书之后，他想计算，他一共执行了多少次翻转操作才能把所有的书排好序。
lmz惊奇地发现，第一次排序之前，他第一次划分出来的所有区间的长度都是偶数。
【输入格式】
第一行一个正整数n, 为书的总数。
接下来n行，每行仅一个正整数hi，为第i本书的高度。
【输出格式】
仅一个整数，为lmz需要做的翻转操作的次数。
【数据规模】
对于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; }
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行，为一个整数，即输入矩阵取数后的最大的分。
【数据规模】
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; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/602585.html