长乐培训Day7
2019-08-16 07:54:19来源:博客园 阅读 ()
长乐培训Day7
T1 删除
题目
【题目描述】
现在,我的手上有 n 个数字,分别是 a1,a2,a3,...,an。 我现在需要删除其中的 k 个数字。当然我不希望随随便便删除,我希望删除 k 数字之后,剩下的 n−k 个数中有最多的不同的数。
【输入格式】
第一行两个正整数 n 和 k,含义如题目描述。 接下来一行,有 n 个非负整数,分别是 a1 到 an。
【输出格式】
一共一行,一个整数ans,表示删除了 k 个数字后最多的不同的数的个数。
【输入样例】
41
1312
【输出样例】
3
【数据规模】
对于 30% 的数据,n≤10,ai ≤10。
对于 60% 的数据,n≤100,ai ≤100。
对于 80% 的数据,n≤10^5,ai ≤10^5。
对于 100% 的数据,n≤10^5,ai ≤10^9。
解析
先排序,后去重,
然后,然后就没有然后了。
Code
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN = 100005; int n, m, k, i, j, a[MAXN]; inline int get() { char c; while (((c = getchar()) < 48 || c > 57) && c != '-'); if (c == '-') { int res = 0; while ((c = getchar()) >= 48 && c <= 57) res = res * 10 + c - '0'; return -res; } else{ int res = c - '0'; while ((c = getchar()) >= 48 && c <= 57) res = res * 10 + c - '0'; return res; } } int main() { //freopen("del.in", "r", stdin); //freopen("del.out", "w", stdout); cin >> n >> k; for(i = 1; i <= n; i ++) a[i] = get(); sort(a + 1, a + 1 + n); m = unique(a + 1, a + 1 + n) - 1 - a; k -= (n - m); if (k <= 0) cout << m; else cout << m - k; //fclose(stdin); //fclose(stdout); }View Code
T2 蚂蚁移动
题目
【题目描述】
有一根尺子,长度L,在上面有N只蚂蚁,且没有两只蚂蚁初始位置相同。每只蚂蚁有一个初始方向(左或者右),且它们会爬行,速度都是每秒一个长度单位。
当它们碰到另外一个蚂蚁或者尺子的边缘时,它们会立即改变移动的方向(即反向)。
给定尺子的长度,蚂蚁的只数,以及所有蚂蚁初始的位置和方向。要你求第T秒时每只蚂蚁的位置。
【输入格式】
第一行两个整数L和T。
第二行一个整数N,表示蚂蚁的只数。
接下来的每行由两部分组成。第一部分是一个整数,表示该蚂蚁的初始位置。第二部分是一个字母,表示初始方向:D表示向右,L表示向左。两部分中间空格。
【输出格式】
N个整数,表示每只蚂蚁的最终位置。无需按照蚂蚁的原先编号输出,只要按照最终位置坐标递增(非降)的顺序输出坐标即可。
【输入样例】
3 5
1
1 D
【输出样例】
0
【数据规模】
L<=200000,N<=70000,N<L,1<=T<=1000000。
解析
非常有趣的题目,当两只蚂蚁相遇时,都会调头,实际上,由于答案无需按照原先编号输出,我们可以直接不处理相遇的情况,
即都调头实际上是没有任何变化的,然后在0点和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 l,t,n,a,b[70100],c; char s; int main() { //freopen("mravi.in","r",stdin); //freopen("mravi.out","w",stdout); l=read(),t=read(),n=read(); for(int i=1;i<=n;i++) { c=0; a=read(),s=getchar(); while(c!=t) { c++; if(s=='D') { if(a==l) { s='L'; a--; } else a++; } else { if(a==0) { s='D'; a++; } else a--; } } b[i]=a; } sort(b+1,b+n+1); for(int i=1;i<=n;i++) cout<<b[i]<<" "; return 0; //fclose(stdin); //fclose(stdout); }View Code
T3 权值
题目
【题目描述】
有一个长度为n的实数序列,,下标从1开始,其中第k个位置的实数为p · (sin(a · k + b) + cos(c · k + d) + 2),
sin和cos采用弧度制,其中p,a,b,c,d均为给定的整数。你需要从这个序列中选择两个位置(可以相同),使前边的位置上的数字减去后边的位置上的数字最大。
如果选择了两个相同的位置,那么差为0.
【输入格式】
一行六个整数p,a,b,c,d,n。
【输出格式】
一行一个实数表示最大的差值,保留六位小数。
【输入样例】
100 432 406 867 60 1000
【输出样例】
399.303813
【数据规模】
对于30%的数据,1<=p,a,b,c,d<=1000,1<=n<=1000;
对于全部的数据,1<=p,a,b,c,d<=1000,1<=n<=10^6。
解析
sin和cos是什么?三角函数?这是个啥?不知道,不过不要紧,直接调用<cmath>库里的sin()和cos()就可以了。
最大的差值如何处理呢?我们先前缀一遍最大值,再后缀一遍最小值,最后两个相减取最大值即可。
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 p,a,b,c,d,n; double maxn,ans[1000001],ans1[1000001],ans2[1000001]; int main() { //freopen("weight.in","r",stdin); //freopen("weight.out","w",stdout); p=read(),a=read(),b=read(),c=read(),d=read(),n=read(); for(int i=1;i<=n;i++) { ans[i]=(double)(p*(sin(a*i+b)+cos(c*i+d)+2)); ans1[i]=max(ans1[i-1],ans[i]); } ans2[n+1]=0x7f7f7f7f; for(int i=n;i>=1;i--) ans2[i]=min(ans2[i+1],ans[i]); for(int i=1;i<=n;i++) maxn=max(maxn,ans1[i]-ans2[i]); printf("%.6f",maxn); return 0; //fclose(stdin); //fclose(stdout); }View Code
T4 dvd的逆序对
题目
【题目描述】
给你n,k求1~n有多少排列有恰好k个逆序对。逆序对:对于i,j,满足i<j,且p[i]>p[j]的点对数
【输入格式】
一行两个整数n,k
【输出格式】
输出一个整数,表示答案对1000000007取模后的结果
【输入样例】
4 1
【输出样例】
3
【数据规模】
对于10%的数据 n<=10
对于30%的数据 k<=50
对于100%的数据 1<=n,k<=1000 且 k<=n*(n-1)/2
解析
很显然这是一道DP题,我们令f[i][j]表示前i个数,逆序对数为j的方案总数。
边界为f[i][0]=1,状态转移方程:f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-i](j>=i)(如果j<i则不用减)
具体原因举个例子试试就知道了。
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; } const int mod=1000000007; int n,k; long long f[1010][1010];//f[i][j]表示前i个数逆序对数为j的方案数 int main() { //freopen("sequence.in","r",stdin); //freopen("sequence.out","w",stdout); n=read(),k=read(); for(int i=0;i<=n;i++) f[i][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=k;j++) f[i][j]=((f[i][j-1]+f[i-1][j])%mod-f[i-1][max(j-i,-1)]+mod)%mod;//f[i-1][-1]=0 cout<<f[n][k]; return 0; //fclose(stdin); //fclose(stdout); }View Code
原文链接:https://www.cnblogs.com/I-Love-You-520/p/11260677.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:长乐培训Day5
- 长乐国庆集训Day1 2019-10-08
- 长乐国庆集训Day4 2019-10-08
- 长乐国庆集训Day5-2 2019-10-08
- 长乐国庆集训Day3 2019-10-08
- 长乐国庆集训Day2 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