dpdpdpdp
题目描述
TT 猫咖的生意越来越红火，人越来越多，也越来越拥挤。
为了解决这个问题，TT 决定扩大营业规模，但猫从哪里来呢？
TT 第一时间想到了神秘人，想要再次通过完成任务的方式获得猫咪。
而这一次，神秘人决定加大难度。
给定一个环，A[1], A[2], A[3], … , A[n]，其中 A[1] 的左边是 A[n]。要求从环上找出一段长度不超过 K 的连续序列，使其和最大。
这一次，TT 陷入了沉思，他需要你们的帮助。
输入
第一行一个整数 T，表示数据组数，不超过 100。
每组数据第一行给定两个整数 N K。（1 ≤ N ≤ 100000, 1 ≤ K ≤ N）
接下来一行，给出 N 个整数。（-1000 ≤ A[i] ≤ 1000）。
输出
对于每一组数据，输出满足条件的最大连续和以及起始位置和终止位置。
如果有多个结果，输出起始位置最小的，如果还是有多组结果，输出长度最短的。
题目分析
代码
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
44
45
46
| #include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
int a[2001000];
inline int read(){
int out = 0,flag = 1;char c = getchar();
while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}
return out * flag;
}
int sum[2001000];
int main(){
int T;
cin>>T;
while(T--){
memset(sum,0,sizeof(sum));
int n,k;
cin>>n>>k;
for(int i =1;i<=n;i++){
a[i+n] = a[i] = read();
sum[i] = a[i] + sum[i-1];
}
for(int i = n+1;i<=n*2;i++){
sum[i] = a[i] + sum[i-1];
}
deque<int> q;
int ans = -inf ,l = 1,r = 1;
q.push_back(0);
for(int i = 1;i<=n*2;i++){
if(q.size() && q.front() < i-k) q.pop_front();
if(ans < sum[i] - sum[q.front()] ){
ans = sum[i] - sum[q.front()];
l = q.front()+1;
r = i>n ? i-n:i;
}
while(q.size() && sum[q.back()] > sum[i]) q.pop_back();
q.push_back(i);
}
printf("%d %d %d\n",ans,l,r);
}
}
|
题目描述
忙碌了一个学期的 Q老师 决定奖励自己 N 天假期。
假期中不同的穿衣方式会有不同的快乐值。
已知 Q老师 一共有 M 件衬衫，且如果昨天穿的是衬衫 A，今天穿的是衬衫 B，则 Q老师 今天可以获得 f[A][B] 快乐值。
在 N 天假期结束后，Q老师 最多可以获得多少快乐值？
输入
输入文件包含多组测试样例，每组测试样例格式描述如下：
第一行给出两个整数 N M，分别代表假期长度与 Q老师 的衬衫总数。（2 ≤ N ≤ 100000, 1 ≤ M ≤ 100）
接下来 M 行，每行给出 M 个整数，其中第 i 行的第 j 个整数，表示 f[i][j]。（1 ≤ f[i][j] ≤ 1000000）
测试样例组数不会超过 10。
输出
每组测试样例输出一行，表示 Q老师 可以获得的最大快乐值。
题目分析
分析题目可以得出，转移方程可以写为：dp[i][B] = max(dp[i-1][k]+f[k][B])
$$
ans[i] = \begin{bmatrix}
dp[i][1] \
\vdots \
dp[i][m]
\end{bmatrix}=\begin{bmatrix}
f[1][1] & \cdots & f[m][1] \
\vdots & \ddots & \vdots \
f[1][m] & \cdots & f[m][m]
\end{bmatrix}\oplus\begin{bmatrix}
f[i-1][1] \
\vdots\
f[i-1][m]
\end{bmatrix}
$$
$\oplus $运算将矩阵乘法的累加换成了max，乘换成了加（符合结合律、交换律）
那么只要构造出中间矩阵，做快速幂即可。
代码
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct matrix{
long long mtx[105][105];
int m,n;
matrix(int n,int m):n(n),m(m){
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++)
mtx[i][j] = 0;
}
matrix operator * (const matrix& x){
matrix ans(n,x.m);
if(m != x.n) return ans;
for(int i = 1;i <= n;i++){
for(int j = 1;j<=x.m;j++){
for(int k = 1;k<= m;k++){
ans.mtx[i][j] = max(ans.mtx[i][j],mtx[i][k]+x.mtx[k][j]);
}
}
}
return ans;
}
void show(){
cout<<"\n";
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
cout<<mtx[i][j]<<" ";
}cout<<"\n";
}
}
};
matrix fast_pow(matrix x,int p){
matrix a(x.n,x.m);
for(;p;p>>= 1,x = x * x){
if(p&1){
a = a * x;
}
}
return a;
}
int main(){
int n,m;
while(cin>>n>>m){
matrix a(m,m);
matrix ori(m,1);
for(int i = 1;i<=m;i++){
ori.mtx[i][1] = 0;
for(int j = 1;j<=m;j++){
cin>>a.mtx[i][j];
}
}
matrix ans = fast_pow(a,n-1) * ori;
long long anss = 0;
for(int i = 1;i<=m;i++){
anss = max(anss,ans.mtx[i][1]);
}
cout<<anss<<"\n";
}
}
|
题目描述
ZJM 收到了 Q老师 送来的生日礼物，但是被 Q老师 加密了。只有 ZJM 能够回答对 Q老师 的问题，Q老师 才会把密码告诉 ZJM。
Q老师 给了 ZJM 一些仅有 01 组成的二进制编码串, 他问 ZJM：是否存在一个串是另一个串的前缀.
输入
多组数据。每组数据中包含多个仅有01组成的字符串，以一个9作为该组数据结束的标志。
输出
对于第 k 组数据(从1开始标号)，如果不存在一个字符串使另一个的前缀，输出”Set k is immediately decodable”，否则输出”Set k is not immediately decodable”。
每组数据的输出单独一行
题目分析
- 直接插入构造字典（？二叉）树
- 把一个字符串每一位放到字典树上，每次新拓展一个节点时++cnt，否则直接移动到已经存在的节点上，过程中如果遇到flag，或者最终移动到已经存在的节点上则直接返回存在前缀，否则返回不存在。
代码
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<iostream>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;
struct rec{
int c[2];
int flag;
}node[200000];
int cnt;
bool insert(string s){
int now = 0;
bool res = 0;
for(int i = 0;i < s.size();i++){
if(node[now].c[s[i]-'0'] == 0){
node[now].c[s[i]-'0'] = ++cnt;
now = cnt;
}else now = node[now].c[s[i]-'0'];
if(node[now].flag == 1) {return true;}
}
node[now].flag = 1;
if(now == cnt) return false;
else return true;
}
int main(){
string s;
bool f = 0;
int k = 1;
while(cin>>s){
if(s[0] == '9'){
if(!f) cout<<"Set "<<k<<" is immediately decodable\n";
else cout<<"Set "<<k<<" is not immediately decodable\n";
f = 0;
memset(node,0,sizeof(node));
cnt = 0;
k++;
}else {
f = insert(s) || f;
}
}
}
|
