95计费法
数据比较小,然后也比较懒.一开始看着B题过的多就先去看B了,结果B愣是不理解题意耗费了很长时间,
简短题意：
给一个长度为 n 的序列 a[1..n]a[1..n]，将其分为 m 段（不可为空），使得每段的 95 分位点大小之和最小。
95 分位点：区间第 len−⌊0.05×len⌋ 小的数，len 表示区间长度（元素个数）。
Input
第一行一个整数 T，表示数据组数。（1≤T≤10）
对于每组数据：
第一行两个整数 n 和 m。（1001≤m≤n≤100）
第二行 n 个整数，表示序列 a。（10000≤a[i]≤1000）
Output
对于每组数据，输出一个整数，表示最小的 95 分位点大小之和。
Sample Input
2
5 2
777 96 114 920 206
5 5
804 253 746 267 487
Sample Output
1126
2557
设f[i][j]为到第i个元素前面分成了j段的最小值,那么f[i][j] = min{f[k][j-1]+(k+1,i)的95分答案}
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
void read(int &x)
{
char c=0;x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
}
int t,n,m;
int a[1001],b[1001],ans=0x3f3f3f3f;
int nie[1001],f[101][101];//f[i][j]//i ->n j->m
inline int cal(int l,int r)
{
if(l==r)return a[l];
for(int i=l;i<=r;i++)
b[i]=a[i];
sort(b+l,b+r+1);
return b[l+nie[r-l+1]-1];
}
int main()
{
for(int i=1;i<=100;i++)
{
nie[i]=i-floor(double(i)*0.05);
}
read(t);
while(t--)
{
memset(f,0x3f3f3f3f,sizeof(f));
read(n),read(m);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<=n;i++)f[i][1]=cal(1,i);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int k=j-1;k<=i-1;k++)
{
f[i][j]=min(f[i][j],f[k][j-1]+cal(k+1,i));
}
}
}
cout<<f[n][m]<<endl;
}
return 0;
}
客户预警
Problem Description
优质的客户资源，是云服务厂商盈利的根本。随着主流云服务厂商同质化竞争越来越激烈，彼此都不惜成本来争夺客户。因此客户挽留成为华为云运营的重要工作。
一般来说，如果用户近 6 个月持续贡献收入，未来 4 个月收入较 6 个月平均收入下降 90% 以上，那么就认为用户流失了。
为了减少用户流失，流失预警就显得尤为重要。我们希望可以引入参数k1 ,k2 ,p，如果一个用户近 k1个月的平均贡献收入少于近k2个月的平均贡献收入的 p%，那么就认为需要给出预警。
具体来说，给定某客户 n 个月贡献的收入，你需要给出一个只含"0""1"的字符串，第 i 个字符表示第 i 个月是否需要给出预警，"1"表示需要，"0"表示不需要。特别地，如果当前的月数不足k2，则认为不需要给出预警。
Input
第一行一个整数 T，表示数据组数。（1≤T≤6）
对于每组数据：
第一行一个正整数 n，表示月数。
第二行 n 个正整数 ai，分别表示每个月的收入。
接下来三个正整数，分别表示 k1,k2,p
1≤k1≤k2≤1e6
0≤p≤100
0≤ai≤1e6
最多只有 3 组数据满足 n>100
Output
一个长度为 n 的 01 串，分别表示在第 ii 个月是否需要给出预警
Sample Input
1
8
4 5 2 9 3 10 1 8
2 4 97
Sample Output
00000011
题意:对于第i天,如果i前面不够k2天则输出0,否则,比较(i到前k2天总和*p/k2)和(i到前k1天总和/k1)大小,前者大输出1否则输出0
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<utility>
#define int long long//记得开long long 我的WA啊..
using namespace std;
void read(int &x)
{
char c=0;x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
}
int t;
int a[1000001],b[1000001];
signed main()
{
read(t);
while(t--)
{
int n;
read(n);
for(int i=1;i<=n;i++)read(a[i]),b[i]=b[i-1]+a[i];//前缀和维护下
int k1,k2,p;
read(k1),read(k2),read(p);
for(int i=1;i<max(k1,k2)&&i<n;i++)cout<<0;
for(int i=max(k1,k2);i<=n;i++)
{
int la=b[i]-b[i-k2],now=b[i]-b[i-k1];
la*=(p*k1);
now*=(100*k2);
if(now<la)cout<<1;
else cout<<0;
}
cout<<endl;
}
return 0;
}
三角函数
当时DFS疯狂剪枝,仍然摆脱不了RE的命运
Input
第一行一个整数 T(1≤T≤10)，表示数据组数。
对于每组数据，输入一行两个整数 p 和 q。1≤p≤q≤1e6 gcd(p,q)=1）
Output
对于每组数据：
若有解，输出一行一个长度不超过 2q 的字符串，表示答案；
若无解，输出一行一个字符串"Noooooooo!"（不含引号）。
Sample Input
2
1 1
1 2
Sample Output
sc
scts
当时没有做出来,赛后看到了ld大佬的代码和ljb大佬有关三角形的演示感到很妙
如果从0向luck数走会很麻烦,我试过dfs必爆栈,在[0,1]里有两个增函数,一个减函数
但是从p和q形成的luck数往0推有一些方向的,反向的话,luck就需要去乘以arcsin,arccos和tan了
在知乎这个回答里我找到了三角函数和反三角函数复合后的结果
如果乘以lucky数的话,前者变成了
后者变成了
当p=q时后者就可以变成0了.基于此就是我下面的代码
博哥将q作为三角形的长边,p作为一条直角边,比较形象地推出了类似的
代码
#include<cstdio>
#include<iostream>
#include<map>
#include<cctype>
#include<cstring>
#include<cmath>
#include<stack>
#define int long long
using namespace std;
void read(int &x)
{
char c=0;x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
}
int t,n,m,p,q;
string wrong="Noooooooo!";
stack<char>ans;
signed main()
{
read(t);
while(t--)
{
cin>>p>>q;
while(p!=q)
{
if(q>p)
{
q-=p;
ans.push('s');
ans.push('t');
}
else if(q<p)
{
p-=q;
ans.push('c');
ans.push('t');
}
}
if(p==q)ans.push('c');
if(ans.size()>2*q)
{
cout<<wrong<<endl;
continue;
}
while(ans.size())
{
cout<<ans.top();
ans.pop();
}
cout<<endl;
}
return 0;
}