Team Round #1: 2019 USP-ICMC

发表于 更新于 分类于 阅读次数： 评论数：
本文字数： 1.1k 阅读时长 ≈ 4 分钟
本文记录了Daenerys Stormborn of the House Targaryen.的第01场训练

Team Round(Training)系列：每周六12：15-17：15
这一场是在9月7日打的，是我们队（Wqr,dqy, Orz btxdy）第一次gym的训练。正好周五凛冬将至训练了这套题，不想找题我就clone了一下。总的来讲难度不算太大。

Status
Status
解了BDGAJF六题。

传送门

A题：单调栈

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
// Author : Wqr_
// Time : 2019/9/7 12:29:41

#include<bits/stdc++.h>
#define iofuck std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int nmax = 1e5 + 50;
int n;
int arr[nmax];
int dis[nmax];
stack<int> st;
int main(){
    iofuck;
    cin >> n;
    memset(dis, -1, sizeof(dis));
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    for(int i = 0; i < n; i++){
        if(!st.empty()){
            while(!st.empty() && arr[i] > arr[st.top()]){
                dis[st.top()] = i;
                st.pop();
            }
        }
        st.push(i);
    }

    /*
    for(int i = 0; i < n; i++){
        cout << dis[i] << " ";
    }
    cout << endl;
    */

    for(int i = 0; i < n; i++){
        if(i) cout << " ";
        if(dis[i] == -1){
            cout << min(arr[i], n - i - 1);
        }else{
            if(dis[i] > arr[i] + i) {
                //cout << arr[i] - i;
                cout << arr[i];
            }else{
                cout << dis[i] - i - 1;
            }
        }
    }
    return 0;
}

B题：因式分解

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;
#define int long long
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define IN freopen("in.txt", "r", stdin);
#define endl '\n'
#define mp make_pair
#define pb push_back
#define lowb lower_bound
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define mem0(a) memset((a), 0, sizeof(a))
#define mem(a, b) memset((a), (b), sizeof(a))
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;

int32_t main(){
    IOS;
    //IN;
    int a, b;
    cin>>a>>b;
    vector<int> vec;
    for(int i = 1; i*i <= a; i++){
        if(a%i==0){
            if(i%b==0)
            vec.push_back(i);
            if(i*i!=a && (a/i)%b==0)vec.push_back(a/i);
        }
    }
    sort(vec.begin(), vec.end());
    for(auto it : vec){
        cout<<it<<' ';
    }
    return 0;
}

D题：找子序列

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define IN freopen("in.txt", "r", stdin);
#define endl '\n'
#define mp make_pair
#define pb push_back
#define lowb lower_bound
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define mem0(a) memset((a), 0, sizeof(a))
#define mem(a, b) memset((a), (b), sizeof(a))
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;

const int maxn = 2e6+10;
char a[maxn], b[maxn];

int32_t main(){
    IOS;
    cin>>a>>b;
    int left = 0, len = strlen(a), len2 = strlen(b);

    for(int i = 0; i < len; i++){
        if(a[i] == b[left]){
            left++;
        }
        if(left == len2){
            break;
        }
    }
    if(left == len2){
        cout<<"YES";
    }else cout<<"NO";
    return 0;
}

F题：冲冲冲！

没看懂没想明白 交上去试试看突然ac的题目

  • 你会吗
  • 不会  那你会吗？
  • 不会
  • 那我感觉是这个答案，交一发把

几十秒钟后………………
dqy🐮🍺

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
 /************************************************
 # @Author:      miniLCT
 # @DateTime:    2019-09-07 16:16:52
 # @Description: You build it.You run it
 ***********************************************/
#include <bits/stdc++.h>

using namespace std;
#define eps 1e-8
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 1e6;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
int main()
{
	int n;
	cin >> n;
	double ans = 1.0*(1+n)  / 2;
	printf("%.10f\n", ans);
}

/******************************************************
 stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?), set tle
  * do smth instead of nothing and stay organized
*******************************************************/

G题：巧克力博弈

严格说是sg博弈。
题意：有三堆石子，两个人轮流拿1~k个石子，谁先拿完谁就赢了。（如果这一堆石子左边堆里还有石子，那么你不能清空这个堆。）
找了几个小的数字之后感觉可以写。
往sg方向想，题意说左边堆会影响右边堆所以最左边堆不受影响，而2，3受影响。我们让第二堆，第三堆少一个石子，这样就没有了限制条件。
sg一下就行。wa了几发是因为写成if(p==0)。。。

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
 /************************************************
 # @Author:      miniLCT
 # @DateTime:    2019-09-07 12:22:26
 # @Description: You build it.You run it
 ***********************************************/
/*
Tomaz  
Danftito
*/
#include <bits/stdc++.h>

using namespace std;
#define eps 1e-8
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 1e6;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
int main()
{
	ll n , a, b , c;
	cin >> n >> a>> b>> c;
	ll p = a % (n+1);
	ll q = (b-1) % (n+1);
	ll r = (c-1) % (n+1);
	ll ans = p^q^r;
	if(ans == 0)cout <<"Danftito"<<endl;
	else cout <<"Tomaz"<<endl; 
}

/******************************************************
 stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?), set tle
  * do smth instead of nothing and stay organized
*******************************************************/

J题：枚举中间的数的素数

这道题lct觉得他可以写，他枚举了第一个数和最后一个数字和中位数的左边右边的各一个素数 感觉很对不可能wa

lct wa的写法

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
 /************************************************
 # @Author:      miniLCT
 # @DateTime:    2019-09-07 12:16:43
 # @Description: You build it.You run it
 ***********************************************/
#include <bits/stdc++.h>

using namespace std;
#define eps 1e-8
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 1e6;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
ll a[maxn];
bool isprime(ll x){
	if(x <= 1)return false;
	//if(x == 0)return true;
	for(ll i = 2; i*i <= x;i++ ){
		if(x%i==0)return false;
	}
	return true;
}
int main()
{
	int n ;
	cin >> n;
	for(int i = 0; i < n;i++){
		cin >> a[i];
	}
	sort(a, a+n);
	ll ans = linf;
	ll res = 0;
	ll kk = a[0]-1;
	while(!isprime(kk)){
		kk--;
		if(kk <= 2)break;
	}
	if(kk <= 2)kk=2;
	for(int i = 0; i < n;i++){
		res += abs(kk - a[i]);
	}
	//cout << "1kk ==="<<kk<<"    res ==="<<res<<endl;
	ans = min(res, ans);

	res = 0;
	kk = a[n-1]+1;
	while(!isprime(kk)){
		kk++;
		//if(kk <= 2)break;
	}
	if(kk <= 2)kk=2;
	for(int i = 0; i < n;i++){
		res += abs(kk - a[i]);
	}
	//cout << "2kk ==="<<kk<<"    res ==="<<res<<endl;
	ans = min(res, ans);

	res = 0;
	kk = a[0]+1;
	while(!isprime(kk)){
		kk++;
		//if(kk <= 2)break;
	}
	//if(kk <= 2)kk=2;
	for(int i = 0; i < n;i++){
		res += abs(kk - a[i]);
	}	
	//cout << "3kk ==="<<kk<<"    res ==="<<res<<endl;
	ans = min(res, ans);

	res = 0;
	kk = a[n-1]-1;
	while(!isprime(kk)){
		kk--;
		if(kk <= 2)break;
	}
	if(kk <= 2)kk=2;
	for(int i = 0; i < n;i++){
		res += abs(kk - a[i]);
	}
	//cout << "4kk ==="<<kk<<"    res ==="<<res<<endl;
	ans = min(res, ans);

	res = 0;
	kk = a[n/2]-1;
	while(!isprime(kk)){
		kk--;
		if(kk <= 2)break;
	}
	if(kk <= 2)kk=2;
	for(int i = 0; i < n;i++){
		res += abs(kk - a[i]);
	}
	//cout << "5kk ==="<<kk<<"    res ==="<<res<<endl;
	ans = min(res, ans);

	res = 0;
	kk = a[n/2]+1;
	while(!isprime(kk)){
		kk++;
		if(kk <= 2)break;
	}
	if(kk <= 2)kk=2;
	for(int i = 0; i < n;i++){
		res += abs(kk - a[i]);
	}
	//cout << "6kk ==="<<kk<<"    res ==="<<res<<endl;
	ans = min(res, ans);


if(isprime(a[0])){
	res = 0;
	kk = a[0];
	if(kk <= 2)kk=2;
	for(int i = 0; i < n;i++){
		res += abs(kk - a[i]);
	}
	//cout << "7kk ==="<<kk<<"    res ==="<<res<<endl;
	ans = min(res, ans);
}
if(isprime(a[n-1])){
	res = 0;
	kk = a[n-1];
	if(kk <= 2)kk=2;
	for(int i = 0; i < n;i++){
		res += abs(kk - a[i]);
	}
	//cout << "8kk ==="<<kk<<"    res ==="<<res<<endl;
	ans = min(res, ans);
}
if(isprime(a[n/2])){
	res = 0;
	kk = a[0];
	if(kk <= 2)kk=2;
	for(int i = 0; i < n;i++){
		res += abs(kk - a[i]);
	}
	//cout << "9kk ==="<<kk<<"    res ==="<<res<<endl;
	ans = min(res, ans);
}
	cout << ans<<endl;
}

/******************************************************
 stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?), set tle
  * do smth instead of nothing and stay organized
*******************************************************/

后来dqy提出可以多找几个最近的素数，复杂度也ok，lct表示赞同但是不想写。

然后dqy开始写，写了几发wa了。百思不得其姐 后来发现是中位数不会写。。lj  dqy！！

dqy ac写法：枚举中间很多个素数 orz dqy

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define IN freopen("in.txt", "r", stdin);
#define endl '\n'
#define mp make_pair
#define pb push_back
#define lowb lower_bound
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define mem0(a) memset((a), 0, sizeof(a))
#define mem(a, b) memset((a), (b), sizeof(a))
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 0x3f3f3f3f3f3f3f3f;

const int maxn = 1e5+10;
int a[maxn];

int n;

ll solve(ll x){
    ll res = 0;
    for(int i = 1; i <= n; i++){
        res += abs(a[i] - x);
    }
    return res;
}

bool isprime(ll x){
    if(x <= 1)return false;
    for(ll i = 2; i*i <= x;i++ ){
        if(x%i==0)return false;
    }
    return true;
}

int32_t main(){
    IOS;
    cin>>n;
    ll sum = 0;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        sum += a[i];
    }
    sort(a+1, a+1+n);
    ll kk = a[(n+1)/2];
    ll res = sum / n;
    ll ans = INF;
    ll sum1 = 0;
    for(ll i = a[1]; ; i++){
        if(isprime(i)){
            sum1++;
            ans = min(solve(i), ans);
        }
        if(i > INF)break;
        if(sum1 == 200)break;
    }
    sum1 = 0;
    for(ll i = a[n]; i;i--){
        if(isprime(i)){
            sum1++;
            ans = min(ans, solve(i));
        }
        if(i <= 1) break;
        if(sum1 == 200)break;
    }
    sum1 = 0;
    for(ll i = res; ;i++){
        if(isprime(i)){
            sum1++;
            ans = min(ans, solve(i));
        }
        if(i > INF)break;
        if(sum1 == 200)break;
    }
    sum1 = 0;
    for(int i = res; i;i--){
        if(isprime(i)){
            sum1++;
            ans = min(ans, solve(i));
        }
        if(i <= 1)break;
        if(sum1 == 200)break;
    }
    sum1 = 0;
    for(int i = a[1]; i; i--){
        if(isprime(i)){
            sum1++;
            ans = min(ans, solve(i));
        }
        if(i <= 1)break;
        if(sum1 == 200)break;
    }
    sum1 = 0;
    for(int i = a[n];  ; i++){
        if(isprime(i)){
            sum1++;
            ans = min(ans, solve(i));
        }
        if(i > INF)break;
        if(sum1 == 200)break;
    }
    sum1 = 0;
    for(int i = kk;;i++){
        if(isprime(i)){
            sum1++;
            ans = min(ans, solve(i));
        }
        if(i > INF)break;
        if(sum1==200)break;
    }
    sum1 = 0;
    for(int i = kk; ;i--){
        if(isprime(i)){
            sum1++;
            ans = min(ans, solve(i));
        }
        if(i <= 1)break;
        if(sum1 == 200)break;
    }
    cout<<ans;
    return 0;
}

补题 ：E,H

E题:dp

这道题本来想最后半小时冲一下的，然后 后面就莫名放弃（提早下班）了…………

可以确定的是排序贪心搞一搞是不行的，dp写

dqy写法

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define int long long
#define IN freopen("in.txt", "r", stdin);
#define endl '\n'
#define mp make_pair
#define pb push_back
#define lowb lower_bound
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define mem0(a) memset((a), 0, sizeof(a))
#define mem(a, b) memset((a), (b), sizeof(a))
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+10;

pii p[maxn];
set<int> s;
pii dp[maxn][6];
int dp2[maxn][6];
map<int, int> msk;
VI vec[maxn];
VI v;

int query(int x, int k){
    int ans = 0;
    for(int i = 0; i < 6; i++){
        ans = max(ans, dp2[k-1][i] + abs(x-dp[k-1][i].se));
    }
    return ans;
}

void query2(int k){
    for(int i = 0; i < 6; i++){
        dp2[k][i] = query(dp[k][i].fi, k);
    }
}

int32_t main(){
    IOS;
    int n; cin>>n;
    int cc = 0;
    for(int i = 0; i < n; i++){
        cin>>p[i].fi>>p[i].se;
    }
    sort(p, p+n);
    for(int i = 0; i < n; i++){
        int x, y;
        x = p[i].fi;
        y = p[i].se;
        if(msk[x]){
            vec[msk[x]].eb(y);
        }else{
            cc++;
            s.insert(cc);
            msk[x] = cc;
            vec[cc].eb(y);
        }
    }
    for(auto it : s){
        v.eb(it);
        sort(all(vec[it]));
    }
    int cnt = 1;
    for(auto it : v){
        if(sz(vec[it]) == 1){
            dp[cnt][0].fi = dp[cnt][0].se = vec[it][0];
            dp[cnt][1].fi = dp[cnt][1].se = vec[it][0];
            dp[cnt][2].fi = dp[cnt][2].se = vec[it][0];
            dp[cnt][3].fi = dp[cnt][3].se = vec[it][0];
            dp[cnt][4].fi = dp[cnt][4].se = vec[it][0];
            dp[cnt][5].fi = dp[cnt][5].se = vec[it][0];
            cnt++;
        }else{
            dp[cnt][0].fi = vec[it][0], dp[cnt][0].se = vec[it][1];
            dp[cnt][1].fi = vec[it][1], dp[cnt][1].se = vec[it][0];
            dp[cnt][2].fi = vec[it][sz(vec[it])-1], dp[cnt][2].se = vec[it][sz(vec[it])-2];
            dp[cnt][3].fi = vec[it][sz(vec[it])-2], dp[cnt][3].se = vec[it][sz(vec[it])-1];
            dp[cnt][4].fi = vec[it][0], dp[cnt][4].se = vec[it][sz(vec[it])-1];
            dp[cnt][5].fi = vec[it][sz(vec[it])-1], dp[cnt][5].se = vec[it][0];
            cnt++;
        }
    }
    for(int i = 1; i < cnt; i++){
        if(i == 1)continue;
        query2(i);
    }
    int ans = 0;
    for(int i = 0; i < 6; i++){
        ans = max(ans, dp2[cnt-1][i]);
    }
    cout<<ans;
    return 0;
}

lct由于对map不是很会用对map操作总有种莫名恐惧，所以对他操作不是很想看下去qwq  他补题写出bug时候也不能为他排忧解难qwq。（ljlct快去训练！）

参考了一下写了一份

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/************************************************
 # @Author:      miniLCT
 # @DateTime:    2019-09-11 18:48:14
 # @Description: You build it.You run it
 ***********************************************/
#include <bits/stdc++.h>

using namespace std;
#define int long long 
#define eps 1e-8
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 1e6+10;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
struct Node{
	int v, p;
}a[maxn];
ll dp[maxn][4],val[maxn][4];
bool cmp(Node a, Node b){
	return a.v < b.v;
}
int dqytxdy[maxn];
int dqyhaoshuai = 0;
std::vector<int > GTMDDQY[maxn];
int b[maxn];  //离散化之后的
int m = 0, n;
void discrete(){
	sort(dqytxdy+1, dqytxdy+1+n);
	for(int i = 1; i <= n;i++){
		if(i == 1 || dqytxdy[i] != dqytxdy[i-1])
			b[++m] = dqytxdy[i];
	}
}
int query(int x){  //查询x映射为1～m之间的整数
	return lower_bound(b+1, b+1+m, x) - b;
}
int32_t main()
{
	close;
	cin >> n ;
	for(int i = 1; i <= n;i++){
		cin >> a[i].v >> a[i].p;
		dqytxdy[++dqyhaoshuai] = a[i].v;
	}
	discrete();
	for(int i = 1; i <= n; i++){
		int dqynb = query(a[i].v);
		GTMDDQY[dqynb].push_back(a[i].p);
	}
	for(int i = 1; i <= m;i++){
		sort(GTMDDQY[i].begin(),GTMDDQY[i].end());
	}
	for(int i = 1; i <= m;i++){
		if(GTMDDQY[i].size()==1)for(int j = 0; j < 4;j++)val[i][j] = GTMDDQY[i][0];
		else if(GTMDDQY[i].size()<=4){
			int j = 0;
			for(; j < GTMDDQY[i].size();j++)val[i][j] = GTMDDQY[i][j];
			for(; j < 4;j++)val[i][j] = -1;
		}
	    else {
	    	val[i][0] = GTMDDQY[i][0];
            val[i][1] = GTMDDQY[i][1];
            val[i][2] = GTMDDQY[i][GTMDDQY[i].size()-2];
            val[i][3] = GTMDDQY[i][GTMDDQY[i].size()-1];
	    }
	}
	ll ans = 0;
	for (int i = 2; i <= m; i++)
		for(int j = 0;j < 4;j++)
	        for(int k = 0;k < 4;k++)
		        for(int l = 0;l < 4;l++){
		            if( val[i-1][k] == -1||val[i][j]==-1 || l==k ) continue;
		            dp[i][j]=max(dp[i][j],dp[i-1][l]+abs(val[i][j]-val[i-1][k]));
		        }
    for(int i=0;i<4;++i) ans=max(ans,dp[m][i]);
    cout << ans<<endl;

}

/******************************************************
 stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?), set tle
  * do smth instead of nothing and stay organized
*******************************************************/

原谅我的变量名，由于这种丑陋变量名导致我调参调了好一会儿

大神写法

三维 滚动数组 orz tttttttttrx!!
orz cust之光

trx天下第一！！

H题：矩阵快速幂优化dp方程

题意

要求这么一个序列：a{i-1}*a{i+1}<=a_{i}^{2},且ai序列只能包括0、1、2.

设dp方程dp[i][j][k]为第i位时，后面两位分别是j、k的方案数。
j，k的取值方案共九种：00 01 02 10 11 12 20 21 22
构造矩阵快速幂的方程：
矩阵快速幂方程
套路啊，套路就完事了。

ac代码

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 /************************************************
 # @Author:      miniLCT
 # @DateTime:    2019-09-11 20:48:36
 # @Description: You build it.You run it
 ***********************************************/

//矩阵快速幂 优化dp 方程
//设dp方程dp[i][j][k]为第i位时，后面两位分别是j、k的方案数。
/*


00           [1 0 0 1 0 0 1 0 0 ] [0 0]
01           [1 0 0 0 0 0 0 0 0 ] [0 1]               
02           [1 0 0 0 0 0 0 0 0 ] [0 2]
10           [0 1 0 0 1 0 0 1 0 ] [1 0]
11     =     [0 1 0 0 1 0 0 0 0 ] [1 1]
12           [0 1 0 0 0 0 0 0 0 ] [1 2]
20           [0 0 1 0 0 1 0 0 1 ] [2 0]
21           [0 0 1 0 0 1 0 0 1 ] [2 1]
22           [0 0 1 0 0 1 0 0 1 ] [2 2]


*/
#include <bits/stdc++.h>

using namespace std;
#define eps 1e-8
#define close ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
const int MAXN = 9;
const int INF = 1e9;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
const ll mod = 1000*1000*1000+7;
ll m[9][9] ={
	{1,0,0,1,0,0,1,0,0},
	{1,0,0,0,0,0,0,0,0},
	{1,0,0,0,0,0,0,0,0},
	{0,1,0,0,1,0,0,1,0},
	{0,1,0,0,1,0,0,0,0},
	{0,1,0,0,0,0,0,0,0},
	{0,0,1,0,0,1,0,0,1},
	{0,0,1,0,0,1,0,0,1},
	{0,0,1,0,0,1,0,0,1}
};

 
struct Matrix
{
	ll mat[MAXN][MAXN];
	Matrix() {}
	Matrix operator*(Matrix const &b)const
	{
		Matrix res;
		memset(res.mat, 0, sizeof(res.mat));
		for (int i = 0; i < MAXN; i++)
		for (int j = 0; j < MAXN; j++)
		for (int k = 0; k < MAXN; k++)
			res.mat [i][j]  = (res.mat[i][j]+this->mat[i][k] * b.mat[k][j])%mod;
		return res;
	}
};
Matrix  pow_mod(Matrix base, ll n)
{
	Matrix res;
	memset(res.mat, 0, sizeof(res.mat));
	for (int i = 0; i < MAXN; i++)
		res.mat[i][i] = 1;
	while (n > 0){
		if (n & 1) res = res*base;
		base = base*base;
		n >>= 1;
	}
	return res;
}
int main()
{
	ll n ;
	Matrix base ;
	for(int i = 0; i < 9; i++)
		for(int j = 0; j < 9;j++)
			base.mat[i][j] = m[i][j];

	cin >> n;
	Matrix ans = pow_mod(base , n-2);
	ll sum = 0 ;
	for(int i = 0 ; i < 9;i++)
		for(int j = 0; j < 9;j++)
			sum =( sum + ans.mat[i][j] ) % mod;

	cout << sum << endl;

}

/******************************************************
 stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?), set tle
  * do smth instead of nothing and stay organized
*******************************************************/

第一次gym还是挺快乐，希望以后可以一直坚持下去，然后有所收获。（补题整整咕咕咕了一礼拜就很尴尬，这周的补题又什么时候呢qwq）

希望正如当初 突然想到的

博观而约取
厚积而薄发

-------------本文结束感谢您的阅读-------------