8题离场，两个人这个水平还可以吧
Ticket
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
北京地铁票每月的打折规则为：本次乘车前总消费不足 100 元本次不打折，满 100 元不足 150 元本次打8 折，满 150 元不足 400 元本次打 5 折，已满 400 元后本次不打折，已知 wls 每次出行的原票价，请问实际的花费是多少?
Input输入包含两行。第一行一个整数 n 代表 wls 将要出行的次数。第二行 n 个正整数, ai 代表每次出行的票的原价，wls 是按照输入顺序依次出行的。
0 ≤ n ≤ 1, 000
0 < ai ≤ 1, 000
Output一行一个数，代表实际的花费，保留小数点后两位小数。
Sample Input
3 100 20 20
Sample Output
132.00
签到
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
while(scanf("%d",&n)!=EOF){
double ans=0;
for(int i=1;i<=n;i++){
int a;
scanf("%d",&a);
if((int)ans<100.0){
ans+=a*1.0;
}
else if(ans<150){
ans+=a*0.8;
}
else if(ans<400){
ans+=a*0.5;
}
else{
ans+=a*1.0;
}
}
printf("%.2lf\n",ans);
}
return 0;
}
Gcd
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Descriptionwls
有一个整数 n，他想将 1 − n 这 n 个数字分成两组，每一组至少有一个数，并且使得两组数字的和的最大公约数最大，请输出最大的最大公约数。
Input输入一行一个整数 n。
2 ≤ n ≤ 1, 000, 000, 000
Output输出一行一个整数表示答案。
Sample Input
6
Sample Output
7
签到，找sum的最小质数因子
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll n;
while(scanf("%lld",&n)!=EOF){
ll ans=(n+1)*n/2;
ll x;
if(n&1){
x=min((n+1)/2,n);
}
else{
x=min(n+1,n/2);
}
int fg=0;
for(int i=2;i*i<=x;i++){
if(x%i==0){
fg=i;
break;
}
}
if(fg==0) fg=x;
printf("%lld\n",ans/fg);
}
return 0;
}
Function
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
wls 有 n 个二次函数 Fi(x) = aix2 + bix + ci (1 ≤ i ≤ n).
现在他想在∑ni=1xi = m 且 x 为正整数的条件下求∑ni=1Fi(xi)的最小值。
请求出这个最小值。
Input第一行两个正整数 n, m。
下面 n 行，每行三个整数 a, b, c 分别代表二次函数的二次项， 一次项，常数项系数。
1 ≤ n ≤ m ≤ 100, 000
1 ≤ a ≤ 1, 000
−1, 000 ≤ b, c ≤ 1, 000
Output一行一个整数表示答案。
Sample Input
2 3 1 1 1 2 2 2
Sample Output
13
优先队列维护一下答案即可，每次x+1对于fun函数的增量是(2*x+1)*a+b，每次放进去增量最小
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct fun{
ll a,b,c;
};
ll f(ll x,fun y){
return y.a*x*x+y.b*x+y.c;
}
struct node{
ll x;
int id;
ll cnt;
bool operator < (const node& y)const{
return x>y.x;
}
};
fun ff[100100];
int main(){
ll n,m;
while(scanf("%lld%lld",&n,&m)!=EOF){
int cnt=(m-n);
priority_queue<node> q;
ll ans=0;
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld",&ff[i].a,&ff[i].b,&ff[i].c);
q.push((node){ff[i].a*3+ff[i].b,i,1ll});
ans+=f(1,ff[i]);
}
while(cnt--){
node x=q.top();
q.pop();
ans+=x.x;
x.cnt++;
q.push((node){ff[x.id].a*(2*x.cnt+1)+ff[x.id].b,x.id,x.cnt});
}
printf("%lld\n",ans);
}
return 0;
}
String
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
wls 有一个长度为 n 的字符串，每次他可以将一个长度不大于 l 的子串修改成同一种字母，问至少修改多少次可以使字符串最多含有 k 段。
连续的只含同 一种字母的子串被称为一段。比如说， aaabbccaaa 共含有 4 段。
Input第一行三个整数 n，l，k。
第二行一个字符串。
1 ≤ n ≤ 100, 000
1 ≤ l ≤ 100, 000
1 ≤ k ≤ 10
Output一行一个数表示答案。
Sample Input
3 1 1 bab
Sample Output
1
区间DP模版题，dp[i][j][k]维护前i个字符分为j段，最后一个字母是k的最小值，dp[i][j][26]记录最小答案
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
const int INF=0x7fffffff;
int n,l,k,dp[maxn][11][27];
char str[maxn];
void init(){
memset(dp,0x3f3f3f3f,sizeof(dp));
rep(j,0,k) rep(c,0,26) dp[0][j][c]=0;
}
void solve(){
init();
scanf("%s",str+1);
rep(i,1,n){
rep(j,1,k){
rep(c,0,25){
if(str[i]==c+'a') dp[i][j][c]=dp[i-1][j][c];
else dp[i][j][c]=dp[i-1][j-1][c];
if(i-l<1){
dp[i][j][c]=min(dp[i][j][c],dp[1][j][c]+1);
dp[i][j][c]=min(dp[i][j][c],dp[1][j-1][26]+1);
}
else{
dp[i][j][c]=min(dp[i][j][c],dp[i-l][j][c]+1);
dp[i][j][c]=min(dp[i][j][c],dp[i-l][j-1][26]+1);
}
dp[i][j][26]=min(dp[i][j][26],dp[i][j][c]);
}
}
}
printf("%d\n",dp[n][k][26]);
}
int main(){
while(~scanf("%d%d%d",&n,&l,&k)) solve();
}
Circle
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
在半径为 1 的圆上有 n 个点，它们也是圆的 n 等分点，将每个相邻的 n 等分点相连，组成了一个正 n边形，现在你可以在圆上再增加一个点，使得新的 n+ 1 边形的面积最大，请输出最大面积。
Input输入有多组（不超过 100 组）。
每组数据一行一个整数 n 代表点的数量。
3 ≤ n ≤ 100
Output每组数据输出一行一个数表示加上一个点后的最大面积，结果保留6位小数。
Sample Input
3
Sample Output
1.732051
简单几何题
#include <bits/stdc++.h>
using namespace std;
const double pi=acos(-1.0);
int main(){
double n;
while(scanf("%lf",&n)!=EOF){
double ans=n*sin(2*pi/n)/2.0;
ans+=(sin(2*pi/(n*2))-sin(2*pi/n)/2.0);
printf("%.6lf\n",ans);
}
return 0;
}
Clock
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
wls 有一个钟表，当前钟表指向了某一个时间。
又有一些很重要的时刻，wls 想要在钟表上复现这些时间（并不需要依次复现）。我们可以顺时针转动秒针，也可以逆时针转动秒针，分针和时针都会随着秒针按规则转动，wls 想知道秒针至少转动多少角度可以使每个时刻至少都会被访问一次。
注意，时钟上的一种时针分针秒针的组合，可以代表两个不同的时间。
Input第一行一个整数 n 代表有多少个时刻要访问。
第二行三个整数 h，m，s 分别代表当前时刻的时分秒。
最后n行每一行三个整数 hi，mi，si 代表每个要访问的时刻的时分秒。
1 ≤ n ≤ 86, 400
0 ≤ h, hi < 24
0 ≤ m, mi, s, si < 60
Output输出一行一个数代表秒钟转的角度，答案保留两位小数。
Sample Input
1 0 1 0 0 1 1
Sample Output
6.00
乱搞题，最终走完必定有两个点之间的距离是没走过的，枚举每对点，更新最小答案
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const double pi=acos(-1.0);
int cal(int x,int y, int z){return x*60*60+y*60+z;}
const int md=43200;
int v[maxn];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
int h,m,s;
scanf("%d%d%d",&h,&m,&s);
h%=12;
int tmp=cal(h,m,s);
v[0]=tmp;
for(int i=1;i<=n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
v[i]=cal(x%12,y,z);
}
sort(v,v+1+n);
int ans=999999999;
for(int i=0;i<=n;i++){
if(v[i]==v[(i+1)%(n+1)]) continue;
if(v[i]==tmp || v[(i+1)%(n+1)]==tmp){
int ma=999999999;
if(v[i]==tmp){
if(n>1) ma=(tmp+md-v[(i+1)%(n+1)])%md;
else ma=min((md+v[(i+1)%(n+1)]-tmp)%md,(tmp+md-v[(i+1)%(n+1)])%md);
}
else{
if(n>1) ma=(md+v[i]-tmp)%md;
else ma=min((md+v[i]-tmp)%md,(tmp+md-v[i])%md);;
}
ans=min(ma,ans);
continue;
}
int ls=(tmp+md-v[(i+1)%(n+1)])%md;
int ln=(v[i]+md-tmp)%md;
ans=min(ans,ls+ln+min(ls,ln));
}
printf("%.2lf\n",(double)ans*6.0);
}
return 0;
}
Tangram
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
一块七巧板有 7 块，现在 wls 想再在七巧板上加 n 条直线将七巧板切分并且使得切出来的块最多，请问最多能有多少块？
Input输入有多组（不超过 100, 000组）。
每组一行一个正整数 n。
0 ≤ n ≤ 1, 000, 000, 000
Output每组输出一行一个数代表答案。
Sample Input
1
Sample Output
13
切一刀这样必定最优，多出6块
再切一刀就是画一条直线越过之前那刀，增加7块，以此类推
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
ll n;
void solve(){
printf("%lld\n",7ll+n*(11+n)/2);
}
int main(){
while(~scanf("%lld",&n)) solve();
}
Tetris
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
wls 有一个 n ∗ m 的网格，他现在想用俄罗斯方块中的"凸"型密铺它。
一个"凸"型占四个格子，你可以随意把它调成上下左右四个方向中的一个。
密铺的定义是网格中任意一个格子被且只被一个"凸"型铺到，并且这些"凸"型不能铺出网格的边界。
随意输出一组解即可。
Input一行两个整数 n, m。
1 ≤ n, m ≤ 12
Output无解输出 no response。
如果有解，输出 n 行，每行 m 个字符。你只能使用 1, 2, 3, 4 这四个字符，由同 一字符组成的四连通块被视为一个"凸"型。
如果有多组解，那么输出任意一种即可。
Sample Input
4 4
Sample Output
1113 2133 2243 2444
签到题
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,m;
int mp[5][5];
void solve(){
if(n%4||m%4) printf("no response\n");
else{
rep(i,1,n){
rep(j,1,m) printf("%d",mp[(i-1)%4+1][(j-1)%4+1]);
printf("\n");
}
}
}
int main(){
mp[1][1]=mp[1][2]=mp[1][3]=mp[2][2]=1;
mp[1][4]=mp[2][3]=mp[2][4]=mp[3][4]=3;
mp[2][1]=mp[3][1]=mp[3][2]=mp[4][1]=2;
mp[3][3]=mp[4][2]=mp[4][3]=mp[4][4]=4;
while(~scanf("%d%d",&n,&m)) solve();
}
