Day24

Day23

今天和学长们一起打了学长们的积分赛。。。
战况还行
补题
OJ链接

小L的项链切割

题目描述
小T送给了小L了一串项链。为了方便,我们把项链上形态不同钻石用不同的字母表示。这样小L的项链就变成了一个字符串。小L忽然想把这串项链优美地切割一下,她想把它切割成尽量少的回文项链,啊也就是回文串。求最少的切割次数。
输入
第一行一个整数T 表示数据组数
下面T组数据,每一组数据:
只有一行,一个只有小写英文字母的字符串,字符串长度 <= 1000。
输出
对于每一组数据,输出将这个字符串能切割成最少的回文串所需切割的次数。

1
2
3
4
5
6
7
样例输入
2
abaacca
abcd
样例输出
1
3

解法
令dp[i]表示从字符串从位置1到位置 i ,最少要切割多少次
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int MAXN = 1e3+7;
int dp[MAXN];
char s[MAXN];

bool check(char *s,int l,int r) {
while(l<=r) {
if(s[l]!=s[r])
return false;
l++;
r--;
}
return true;
}

int main() {
int t;
scanf("%d",&t);
while(t--) {
scanf("%s",s+1);
int len = strlen(s+1);
memset(dp,0,sizeof(dp));
for(int i=1;i<=len;++i) {
dp[i] = MAXN;
for(int j=1;j<=i;++j) {
if(check(s,j,i)) {
if(j==1)
dp[i] = 1;
else
dp[i] = min(dp[i],dp[j-1]+1);
}
}
}
printf("%d\n",dp[len]-1);
}
return 0;
}

小L的试卷

Description:
题目描述
小L期末考试结束,高高兴兴放假回家了,可是那么多试卷,老师还要加班批改,有n份试卷由k个老师批改,n份试卷进行了密封编号,由于试卷上的做题情况和书写的规范程序不一样,批改不同的试卷用时也可能不一样,每个老师批改试卷的编号顺序是连续的,每位老师批改完分配给自己的试卷就可以离开,问最后离开的老师,最短可能的用时是多少,假定一份试卷让任何一位老师批改用时都是一样的。现在请你设计一种分配方案,使得最后离开的老师用时最短。
输入
第一行两个整数n,k;(0<k≤n≤1000)
第二行n个整数,第i个整数表示批改第i份试卷的用时。
输出
输出一个整数,表示最后离开的老师所用的最短时间

1
2
3
4
5
样例输入
9 3
1 2 3 4 5 6 7 8 9
样例输出
17

二分求解
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f;
const int maxn = 1e5 + 10;

int n , k;
ll a[maxn];

bool isok(int x)
{
bool flag = false;
int num = 0;
ll temp = 0;
for (int i=1; i<=n; i++)
{
if (a[i] > x) return false;
temp += a[i];
if (temp > x)
{
num ++;
temp = a[i];
}
}
if (temp > 0) num ++;
if (num <= k) return true;
else return false;
}
int main()
{
scanf("%d%d", &n, &k);
for (int i=1; i<=n; i++) scanf("%lld", &a[i]);
ll l = 0 , r = inf;
while (l <= r)
{
int mid = (l + r) / 2;
if (isok(mid)) r = mid-1;
else l = mid + 1;
}

cout << l << endl;
return 0;
}

小L记单词

Description:
题目描述
小L最近在努力学习英语,但是对一些词组总是记不住,小L小把这些词组中每一个单词的首字母都记一下,这样形成词组的缩写,通过这种方式小L的学习效率明显提高。
输入
输入有多行,每组测试数据占一行,每行有一个词组,每个词组由一个或多个单词组成;每组的单词个数不超过10个,每个单词由大、小写字母组成;
单词长度不超过10,由一个空格分隔这些单词。
输出
对应每一个词组,输出词组的缩写,缩写都用大写字母,每组输出占一行。

1
2
3
4
样例输入
end of file
样例输出
EOF

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxx = 110;
int main()
{
string str;
char a[maxx];
while(getline(cin,str))
{
memset(a, 0, sizeof a);
a[0] = str[0];
int len = 1;
for(int i = 1; i < str.size(); i ++)
{
if(str[i - 1] == ' ')
a[len ++] = str[i];
else continue;
}
for(int i = 0; i < len; i ++)
{
if(a[i] >= 'a' && a[i] <= 'z')
a[i] -= 32;
else if(a[i] >= 'A' && a[i] <= 'Z')
continue;
}
for(int i = 0; i < len; i ++)
cout << a[i];
puts("");
}
return 0;
}

小L的取膜算式

Description:
题目描述
小L想请你帮忙计算一下这个式子的结果
(a+b)p MOD p,其中p是质数。
输入
多组数据
第一行一个T表示数据组数
接下来T行,每行3个正整数a, b, p且保证p是质数 ,输入数据都是long long范围内的正整数。特别的: p <= 2^62
输出
对于每一组输入数据,输出正确结果

1
2
3
4
5
样例输入
1
1 2 3
样例输出
0

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll T, a, b, p;
scanf("%lld",&T);
while(T --)
{
scanf("%lld %lld %lld",&a, &b, &p);
a %= p;
b %= p;
ll ans = (a + b) % p;
printf("%lld\n",ans);
}
return 0;
}

小L玩滚球游戏

Description:
题目描述
小L正在玩滚球游戏,有n个水晶球在轨道上以不同开始位置和速度从近往远的方向滚动,如果两个水晶球在滚动过程中相遇,它们就会融合成一个水晶球,然后以速度较慢的水晶球的速度继续向前滚动, 问经过时间t后,轨道上还有多少水晶球。
输入
第一行输入两个整数n、t,n代表水晶球的数量(1 <= n <= 105, 0<t<231),t代表时间。
接下来n行,每行两个整数,按位置从近到远的顺序给出水晶球的初始位置和速度。
输出
输出一个整数表示经过时间t后水晶球的数量。

1
2
3
4
5
6
7
8
9
样例输入
5 3
0 1
1 2
2 3
3 2
6 1
样例输出
3

题解:

根据题意,移动速度快的球可能会追上在他前面移动速度慢的球,并且追上后合并在一起会变成前面速度慢的球。
可以将题意理解为,后面移动速度快的球碰到前面移动速度慢的球则会消失。
而且t是固定的值,直接计算每个位置在t秒后移动到的位置,逆向维护一个最靠后的值,检测当前球是否超过这个值。
如果超过则说明追上了后面的球当前球会消失。
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <bits/stdc++.h>
#define fst first
#define sed second
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 10;
int a[N], v[N];
ll b[N]; //经过t秒所处位置

int main()
{
#ifdef LOCAL
//freopen("C:/input.txt", "r", stdin);
#endif
int n, t, m = 0;
cin >> n >> t;
for (int i = 1; i <= n; ++i)
scanf("%d%d", &a[i], &v[i]), b[i] = a[i] + 1LL * v[i] * t;
ll p = LINF;
for (int i = n; i >= 1; --i)
{
if (b[i] >= p)
m++;
p = min(p, b[i]);
}
cout << n - m << endl;

return 0;
}

小L的区间求和

Description:
题目描述
在给定的一个整数序列中,小L希望找到一个连续的区间,这个区间的和能够被k整除,请你帮小L算一下满足条件的最长的区间长度是多少。
输入
第一行输入两个整数n、k。(1 <= n <= 105,1<=k<100)
接下来一行输入n个整数,表示序列中的数。
输出
输出一个整数,满足条件区间的最长长度,如果不存在,输出0

1
2
3
4
5
样例输入
5 7
1 2 4 1 1
样例输出
3

题解:

题解:开一个数组要来记录前n项对K取余的余数,,再开一个数组,用来记录余数第一次出现的位置
要点1 当一个 余数数组 的的前几项和为0的时候,从开头到此处的和是K的倍数
要点2 当一个余数重复出现的时候,说明从该余数第一次出现的位置(不包括第一次)到该次出现的位置的和味K的倍数(仔细想想还是很有道理的)
例如 2%10=2 (2+10)%10 =2 所以当两个余数相同时,期间一定加上了k的倍数。关键就是前面的前n项和的余数数组有点难理解。}
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
const int maxx = 1e5;
int a[maxx], sum[maxx];
int main()
{
int n, k;
scanf("%d %d",&n, &k);
map<int, int> mp;
for(int i = 1; i <= n; i ++)
{
scanf("%d",&a[i]);
sum[i] = (sum[i - 1] + a[i]) % k;
mp[sum[i]] = -1;
}
int ans = 0;
mp[sum[0]] = 0;
for(int i = 1; i <= n; i ++)
{
if(mp[sum[i]] == -1)
mp[sum[i]] = i;
else
ans = max(ans, i - mp[sum[i]]);
}
printf("%d\n",ans);

return 0;
}

小L的随机数

Description:
题目描述
随机数是生成随机算法的基础,小L准备使用线性同余法(Linear Congruential Method)来生成一个随机数列,这种方法需要设置四个非负整数参数m, a, c, x0按照下面的公式生成出一系列随机数 : Xn+1 = (a * Xn + c) mod m ,小L现在想知道这个数列第n个数是多少,由于他只需要生成小于g的随机数,所以你只需要告诉他Xn mod g的结果即可。
输入
输入一行6个整数,分别表示m, a, c, X0, n, g 。(n ≤ 106,1 ≤ m, a, c, X0 , g ≤231 − 1)
输出
一行一个整数表示Xn

1
2
3
4
样例输入
233 3 3 3 3 333
样例输出
120

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e7 + 50;

int main()
{
ll m, a, c, x, n, g;
cin >> m >> a >> c >> x >> n >> g;
for(int i = 1; i <= n; i ++)
{
x = (x * a + c) % m;
}

printf("%lld\n",x % g);

return 0;
}

小L的直线

Description:
题目描述
小学时期的小L发现自己很有艺术细胞,于是买了一块画板,但是他的绘画水平使得他只能连接两点画出一条线段。有一天他决定在一张有n个点的图上作画,即他可以把这n个点任意连接。大家认为平行线是非常不美观的,于是他想知道自己最多能画多少条直线使整张画不出现平行线。
输入
第一行输入一个整数n (1 <= n <= 200)
接下来n行每行两个整数代表每个点的坐标x, y (-1000 <= x, y <= 1000)
输出
一行一个整数为能画出最多的两两不平行的直线条数

1
2
3
4
5
6
7
8
样例输入
4
-1 1
-2 0
0 0
1 1
样例输出
4

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
const int maxx = 1e3;
struct node{
int x, y;
}e[maxx];
int main()
{
int n;
set<double> se;
scanf("%d",&n);
for(int i = 0; i < n; i ++)
cin >> e[i].x >> e[i].y;
double ans;
int cnt = 0;
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < n; j ++)
{
if(i == j) continue;
else
{
if((e[j].x - e[i].x) == 0) cnt = 1;
else
{
ans = 1.0 * (e[j].y - e[i].y) / (e[j].x - e[i].x);
se.insert(ans);
}

}
}
}
// for(set<double> :: iterator it = se.begin(); it != se.end(); it ++)
// cout << *it << " ";
cout << se.size() + cnt << endl;
return 0;
}

小L的长方形

Description:
题目描述
在数学课上,老师发给小L一根铁丝,让小L将这根铁丝围成一个长方形。要求这个长方形的长是宽的3倍,并且计算它的面积。
输入
仅一个整数a,表示铁丝的长度(a≤10000)。
输出
输出三个数,分别表示长方形的长、宽、面积。如果计算结果是整数,则输出整数结果(没有小数部分);如果不是,则保留三位小数。每个数之间用一个空格隔开。

1
2
3
4
样例输入
36
样例输出
13.500 4.500 60.750

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

int main()
{
double x;
double l;
cin >> l;
x = l / 8;
double ans = 3 * x * x;
if(x == (int)x)
printf("%.0lf %.0lf %.0lf\n",3 * x, x, ans);
else
printf("%.3lf %.3lf %.3lf\n",3 * x, x, ans);


return 0;
}

---------------- The End ----------------
0%