长乐培训Day7
t1 删除
题目
【题目描述】
现在，我的手上有 n 个数字，分别是 a1,a2,a3,...,an。 我现在需要删除其中的 k 个数字。当然我不希望随随便便删除，我希望删除 k 数字之后，剩下的 n−k 个数中有最多的不同的数。
【输入格式】
第一行两个正整数 n 和 k，含义如题目描述。 接下来一行，有 n 个非负整数，分别是 a1 到 an。
【输出格式】
一共一行，一个整数ans，表示删除了 k 个数字后最多的不同的数的个数。
【数据规模】
对于 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);
}
t2 蚂蚁移动
题目
【题目描述】
有一根尺子，长度l，在上面有n只蚂蚁，且没有两只蚂蚁初始位置相同。每只蚂蚁有一个初始方向（左或者右），且它们会爬行，速度都是每秒一个长度单位。
当它们碰到另外一个蚂蚁或者尺子的边缘时，它们会立即改变移动的方向（即反向）。
给定尺子的长度，蚂蚁的只数，以及所有蚂蚁初始的位置和方向。要你求第t秒时每只蚂蚁的位置。
【输入格式】
第一行两个整数l和t。
第二行一个整数n，表示蚂蚁的只数。
接下来的每行由两部分组成。第一部分是一个整数，表示该蚂蚁的初始位置。第二部分是一个字母，表示初始方向：d表示向右，l表示向左。两部分中间空格。
【输出格式】
n个整数，表示每只蚂蚁的最终位置。无需按照蚂蚁的原先编号输出，只要按照最终位置坐标递增（非降）的顺序输出坐标即可。
【数据规模】
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);
}
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。
【输出格式】
一行一个实数表示最大的差值，保留六位小数。
【数据规模】
对于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);
}
t4 dvd的逆序对
题目
【题目描述】
给你n,k求1~n有多少排列有恰好k个逆序对。逆序对：对于i,j,满足i<j，且p[i]>p[j]的点对数
【输入格式】
一行两个整数n,k
【输出格式】
输出一个整数，表示答案对1000000007取模后的结果
【数据规模】
对于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);
}
蚂蚁移动