9.7 剑心互娱

一、前言

由于和滴滴笔试撞了，写的急的很，0.5 + 0.058 + 0

第一题本来能ac的，少写了个方向，第二题看佬们分享的思路赛后写的，不知道对不对，有没有过的佬看一下。

剑心应该没了

滴滴最后一题区间dp，板子记混了，就拿了0.36,真的能被自己蠢死，比完之后焦虑的睡不着，艹,冷静之后，爬起来又过来写题解了。

9场笔试，0面试，双非鼠，感觉秋招好难阿，纯当分母。

二、题解

1、

样例

输入

5,5
0,0,0,0,0 
0,1,1,0,0 
0,0,1,1,0
0,0,1,0,0 
0,0,1,0,0

输出

思路

枚举4个方向，并且标记这个方向是否走过

时间复杂度O(nm)

#include<bits/stdc++.h>
using namespace std;
/*#define int long long*/
#define endl '\n'
#define P pair<int, int>
#define x first
#define y second
const int maxl = 1e3 + 7;

int n, m, ans = 0;
int G[maxl][maxl];
bool flag1[maxl][maxl], flag2[maxl][maxl], flag3[maxl][maxl], flag4[maxl][maxl];
char ch;

void f1(int x, int y) {
    int res = 0;

    while (G[x][y]) {
        flag1[x][y] = 1;
        res++;
        y++;
    }
    ans = max(ans, res);
}

void f2(int x, int y) {
    int res = 0;

    while (G[x][y]) {
        flag2[x][y] = 1;
        res++;
        y++;
        x++;
    }
    ans = max(ans, res);
}

void f3(int x, int y) {
    int res = 0;

    while (G[x][y]) {
        flag3[x][y] = 1;
        res++;
        x++;
    }
    ans = max(ans, res);
}

// 这个方向我忘写了，艹
void f4(int x, int y) {
    int res = 0;

    while (G[x][y]) {
        flag3[x][y] = 1;
        res++;
        x--;
        y++;
    }
    ans = max(ans, res);
}




void solve() {
    cin >> ch;
    n = ch - '0';
    cin >> ch >> ch;
    m = ch - '0';
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> ch;
            G[i][j] = ch - '0';
            if (j != m) cin >> ch;
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!G[i][j]) continue;
            if (!flag1[i][j]) f1(i, j);
            if (!flag2[i][j]) f2(i, j);
            if (!flag3[i][j]) f3(i, j);
        }
    }
    cout << ans << endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    /*cin >> t;*/
    while(t--) solve();
    return 0;
}

2、

样例

输入

10 2 1 5 2 5

输出

思路

由于这里没有给数据范围，我猜如果t很大，t1和t2很小，那么这样就可以过了。如果有佬过了，麻烦说一下这样对不对，还是说还有其他优化方案。

用最小公倍数算周期
只需要算出一个周期内的变化就行了

时间复杂度O(lcm(2 * t1, t * t2))

#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
/*#define int long long*/
#define endl '\n'
#define P pair<int, int>
#define x first
#define y second
const int maxl = 1e6 + 7;

int m ,t, m1, t1, m2, t2;
int T, cm, ct;
int cnt;

int f() {
        int water = 0;
        /*cout << "时间(分)\t" << "增水量\t" << "减水量\t" << "剩余水量\t" << endl;*/
        /*cout << string(45, '-') << endl;*/

        for (int i = 0; i < T; ++i) {
            int increase = 0, decrease = 0;
             // 排水
            if (i % (t2 * 2) < t2) water -= m2, decrease = m2;
            // 进水
            if (i % (t1 * 2) < t1) water += m1, increase = m1;
            water = min(m, max(0, water));    
            if (i + 1 == ct) cm = water;
            /*cout << i + 1 << "\t\t" << increase << '\t' << decrease << '\t' << water << endl;*/
        }
        return water;
}

void solve() {
    cin >> m >> t >> m1 >> t1 >> m2 >> t2;
    T = 4 * t1 * t2 / __gcd(t1 * 2, t2 * 2);
    ct = t % T;
    cnt = t / T;
    cout << cnt * f() + cm << endl;
    /*cout << "ct: " << ct << '\t' << " cm: " << cm << endl;*/
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    /*cin >> t;*/
    while(t--) solve();
    return 0;
}