差分法

对于一个 将区间[l, r]整体增加一个值 v 操作，我们可以对差分数组 c 的影响看成两部分：

对 b[l] += v：由于差分是前缀和的逆向过程，这个操作对于将来的查询而言，带来的影响是对于所有的下标大于等于 l 的位置都增加了值 v；
对 b[r + 1] -= v：由于我们期望只对 [l, r]产生影响，因此需要对下标大于 r的位置进行减值操作，从而抵消“影响”。

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
#include<iostream>

using namespace std;

const int N = 100010;
int n,m;
int a[N],b[N];

void insert(int l,int r,int c){
    b[l] += c;
    b[r+1] -= c;
}

int main(){
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) insert(i,i,a[i]);//将a[i]依次插入数组
    
    while(m--){
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        insert(l,r,c);
    } 
    
    for(int i=1;i<=n;i++) b[i] += b[i-1];//求b前n项和
    for(int i=1;i<=n;i++) printf("%d ",b[i]);
    
    return 0;
    
}

【邻接表】STL中的vector实现邻接表

1
2
3
4
5
struct Edge{ //边表节点类型
    int to, w; //顶点序号和边长
};

vector<vector<Edge>>maps;

202203-2出行计划

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<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;

vector<vector<ll>>tt;

int main()
{
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll>cnt(200005, 0);

    //差分算法
    for (ll i = 0; i < n; i++) {
        ll t1, t2;
        cin >> t1 >> t2;

        if (t1 - t2 + 1 >= 1)cnt[t1 - t2 + 1]++;
        else cnt[1]++;
        cnt[t1 + 1]--;
    }
    //前缀和
    for (ll i = 2; i < 200005; i++) {
        cnt[i] += cnt[i - 1];
    }

    for (ll i = 0; i < m; i++) {
        ll q;
        cin >> q;
        q += k;
        cout << cnt[q] << endl;
    }

    return 0;
}

202112-2序列查询新解

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2e5+10;
int n,m,k,t,c,q;
int cnt[N];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&t,&c);
        int x=t+1-k-c,y=t-k;
        if(y<=0) continue;  //上界不能小于0，不然没意义
        x=max(1,x);  //下界不能小于1，不然是没意义的
        //cout<<x<<" "<<y<<" "<<i<<endl;
        cnt[x]++;    //差分
        cnt[y+1]--;
    }
    for(int i=1;i<=200000;i++) cnt[i]+=cnt[i-1];  //计算前缀和
    while(m--)
    {
        scanf("%d",&q);   //O（1）的查询操作
        printf("%d\n",cnt[q]);
    }
    return 0;
}

202112-3登机牌条码

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<unordered_map>
#define ll long long
using namespace std;

vector<ll> toDn(string str,ll w,ll s) {
    ll flag = 1;
    vector<ll>result;
    
    for (ll i = 0; i < str.length(); i++) {
        ll nflag = 1;
        if (str[i] >= 'A' && str[i] <= 'Z')nflag = 1;
        else if (str[i] >= 'a' && str[i] <= 'z')nflag = 2;
        else if (str[i] >= '0' && str[i] <= '9')nflag = 3;
        

        if (flag == 1 && nflag == 2)result.push_back(27);
        else if (flag == 1 && nflag == 3)result.push_back(28);
        else if (flag == 2 && nflag == 1) {
            result.push_back(28);
            result.push_back(28);
        }
        else if (flag == 2 && nflag == 3)result.push_back(28);
        else if (flag == 3 && nflag == 2)result.push_back(27);
        else if (flag == 3 && nflag == 1)result.push_back(28);

        flag = nflag;
        if (flag == 1)result.push_back(str[i] - 'A');
        else if (flag == 2)result.push_back(str[i] - 'a');
        else if (flag == 3)result.push_back(str[i] - '0');
    }
    if (result.size() % 2 == 1)result.push_back(29);

    vector<ll>mazi(result.size() / 2, 0);
    for (ll i = 0; i < result.size(); i += 2) {
        mazi[i / 2] = result[i] * 30 + result[i + 1];
    }

    ll k = pow(2, s + 1);
    if (k == 1)k = 0;

    ll len9 = (ll)mazi.size() + (ll)1 + k;
    len9 = (w - (len9 % w)) % w;
    while (len9--)mazi.push_back(900);

    return mazi;
}

vector<ll> calGx(ll k) {
    vector<ll>ans{-3,1};				//X - 3
    ll powl = 3;
    for (ll i = 2; i <= k; i++) {	
        ll len = ans.size();	
        powl = -abs((3 * powl) % 929);
        vector<ll>tmp(len + 1, 0);		//X的下一次方
        
        for (ll j = 0; j < len; j++) {	
            tmp[j] = ans[j] * powl % 929;
        }
        for (ll j = 0; j < len; j++) {
            tmp[j+1] += ans[j] % 929;
        }
        ans = tmp;
    }
    return ans;
}

vector<ll> calCrx(vector<ll> dn, vector<ll> gx,ll k) {
    ll len = dn.size();
    vector<ll>kdx(len + k + 1, 0);
    for (ll i = 0; i < len; i++)
        kdx[i + k] = dn[len - i - 1] % 929;
    kdx[len + k] = len + 1;

    //计算kdx模gx的余数
    ll lenkdx = kdx.size();
    ll lengx = gx.size();
    
    for (ll n = lenkdx - 1; n >= lengx - 1; n--) {
        ll mul = kdx[n] / gx[lengx - 1];
        mul %= 929;
        for (ll i = lengx - 1, j = 0; i >= 0; i--,j++) {
            kdx[n - j] -= mul * gx[i];
            kdx[n - j] = (kdx[n - j] % 929 + 929) % 929;
        }
    }
    vector<ll>crx = vector<ll>(kdx.begin(), kdx.begin() + lengx - 1);
    for (auto& x : crx) {
        x = -x;
        x = (x % 929 + 929) % 929;
    }
    reverse(crx.begin(), crx.end());
    return crx;
}

int main()
{
    ll w, s;
    cin >> w >> s;
    string str;
    cin >> str;
    vector<ll>dn = toDn(str,w,s);
    cout << dn.size() + 1 << endl;
    for (auto x : dn) {
        cout << x << endl;
    }

    ll k = (1 << (s + 1));
    if (k != 1) {
        vector<ll> crx = calCrx(dn, calGx(k), k);
        for (auto x : crx) {
            cout << x << endl;
        }
    }	

    return 0;
}

202109-1数组推导

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
#include<iostream>

using namespace std;
#define ll long long
//6
//0 0 5 5 10 10

int main()
{
    ll n;
    cin >> n;
    
    ll last, cur;
    cin >> last;
    ll mins = last, maxs = last;

    for (ll i = 1; i < n; i++) {
        cin >> cur;
        if (cur == last)maxs += cur;
        else {
            mins += cur;
            maxs += cur;
        }
        last = cur;
    }

    cout << maxs << endl << mins;

    return 0;
}

202109-2非零段划分

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
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int>a(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    a.erase(unique(a.begin(), a.end()), a.end());

    vector<int>cnt(10005, 0);

    for (int i = 1; i < a.size() - 1; i++) {
        if (a[i] > a[i - 1] && a[i] > a[i + 1])
            cnt[a[i]]++;
        else if (a[i] < a[i - 1] && a[i] < a[i + 1])
            cnt[a[i]]--;
    }

    int preSum = 0, ans = 0;
    for (int i = 10004; i >= 0; i--) {
        preSum += cnt[i];
        if (preSum > ans) {
            ans = preSum;
        }
    }
    cout << ans << endl;
}

202109-03脉冲神经网络

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
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
#define db double
using namespace std;


static unsigned long mynext = 1;

/* RAND_MAX assumed to be 32767 */
int myrand(void) {
    mynext = mynext * 1103515245 + 12345;
    return((unsigned)(mynext / 65536) % 32768);
}

struct Edge {
    ll s;
    ll t;
    db w;
    ll D;
    Edge(ll ts, ll tt, db tw, ll tD) {
        s = ts; t = tt; w = tw; D = tD;
    }
};
vector<Edge>maps[2005];
ll N, S, P, T;
db delt;

db v[2005], u[2005], a[2005], b[2005], c[2005], d[2005];//神经元
ll times[2005];
db r[2005], Ik[2005][1005];//脉冲源


int main()
{

    cin >> N >> S >> P >> T;// N 个神经元， S个突触和  P个脉冲源

    cin >>delt;
    // N 个神经元
    for (ll i = 0; i < N;) {
        ll tn;
        db tv, tu, ta, tb, tc, td;
        cin >> tn >> tv >> tu >> ta >> tb >> tc >> td;
        for (ll j = 0; j < tn; j++) {
            v[i + j] = tv; 
            u[i + j] = tu;
            a[i + j] = ta;
            b[i + j] = tb;
            c[i + j] = tc; 
            d[i + j] = td;
        }
        i += tn;
    }
    // P个脉冲源
    for (ll i = 0; i < P; i++) {
        cin >> r[N + i];
    }
    // S个突触
    for (ll i = 0; i < S; i++) {
        ll ts, tt, td;
        db tw;
        cin >> ts >> tt >> tw >> td;
        maps[ts].push_back(Edge(ts, tt, tw, td));
    }



    for (ll i = 1; i <= T; i++) {
        
        //所有脉冲源判断r大小是否符合
        for (ll j = N; j < N + P; j++) {
            
            if (myrand() < r[j]) {
                for (auto edge : maps[j]) {
                    Ik[edge.t][(i + edge.D)%1000] += edge.w;
                }
            }
        }

        //所有神经元更新
        for (ll j = 0; j < N; j++) {
            db oldv = v[j];
            v[j] = v[j] + delt * (0.04 * v[j] * v[j] + 5 * v[j] + 140 - u[j]) + Ik[j][i%1000];
            u[j] = u[j] + delt * a[j] * (b[j] * oldv - u[j]);
            if (v[j] >= 30.0) {
                times[j]++;
                for (auto edge : maps[j]) {
                    Ik[edge.t][(i + edge.D) % 1000] += edge.w;
                }
                v[j] = c[j];
                u[j] = u[j] + d[j];
            }
            //cout << "v: " << v[j] << endl;
        }

    }

    ll mint = LONG_MAX, maxt = 0;
    db minv = 999999999.0, maxv = -999999999.0;
    for (ll i = 0; i < N; i++) {
        minv = min(minv, v[i]);
        maxv = max(maxv, v[i]);
        mint = min(mint, times[i]);
        maxt = max(maxt, times[i]);

    }	
    printf("%.3f %.3f\n", minv, maxv);
    printf("%lld %lld\n", mint, maxt);


    return 0;
}

202104-3DHCP服务器

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
153
154
155
156
157
158
159
160
161
162
163
164
165
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#define ll long long
#define dd double
using namespace std;

ll N, Tdef, Tmax, Tmin;
ll n;
string H;


//status:1,2,3,4 --> 未分配、待分配、占用、过期
struct IP {
    ll status;
    string user;
    ll expire;
    IP() {
        status = 1;
        user = "";
        expire = 0;
    }
};
vector<IP>IPool;

ll getUser(string u) {
    ll ret = 0;
    for (ll i = 1; i <= N; i++) {
        if (IPool[i].user == u) {
            ret = i;
            break;
        }
    }
    return ret;
}

ll getMin1() {
    ll ret = 0;
    for (ll i = 1; i <= N; i++) {
        if (IPool[i].status == 1) {
            ret = i;
            break;
        }
    }
    return ret;
}
ll getMin4() {
    ll ret = 0;
    for (ll i = 1; i <= N; i++) {
        if (IPool[i].status == 4) {
            ret = i;
            break;
        }
    }
    return ret;
}
void setUnused(string u) {
    for (ll i = 1; i <= N; i++) {
        if (IPool[i].user == u && IPool[i].status == 2) {
            IPool[i].status = 1;
            IPool[i].user = "";
            IPool[i].expire = 0;
        }
    }
}
void setExpire(ll ip,ll ti,ll expired) {
    if (expired == 0) {
        IPool[ip].expire = ti + Tdef;
    }
    else if (expired >= ti + Tmin && expired <= ti + Tmax) {
        IPool[ip].expire = expired;
    }
    else if (expired > ti + Tmax) {
        IPool[ip].expire = ti + Tmax;
    }
    else if (expired < ti + Tmin) {
        IPool[ip].expire = ti + Tmin;
    }
}
void handleTime(ll ti) {
    for (ll i = 1; i <= N; i++) {
        if (IPool[i].expire != 0 && IPool[i].expire <= ti) {
            if (IPool[i].status == 2) {
                IPool[i].user = "";
                IPool[i].status = 1;
                IPool[i].expire = 0;
            }
            else {
                IPool[i].status = 4;
                IPool[i].expire = 0;
            }
        }
    }
}




int main()
{
    cin >> N >> Tdef >> Tmax >> Tmin >> H;
    IPool = vector<IP>(N + 1);
    cin >> n;
    while (n--)
    {
        ll ti, ip, expired;
        string des, to, mes;
        cin >> ti >> des >> to >> mes >> ip >> expired;

        if (!(to == "*" || to == H) && mes != "REQ")continue;
        if (mes == "OFR" || mes == "ACK" || mes == "NAK")continue;
        if ((to == "*" && mes != "DIS") || (to == H && mes == "DIS"))continue;

        handleTime(ti);

        //未分配、待分配、占用、过期
        if (mes == "DIS") {

            ll outip = 0;
            if (getUser(des) != 0) {//占用
                outip = getUser(des);
            }
            else if (getMin1() > 0) {
                outip = getMin1();
            }
            else if (getMin4() > 0) {
                outip = getMin4();
            }
            else {

            }

            if (outip == 0) {
                continue;
            }

            IPool[outip].status = 2;
            IPool[outip].user = des;
            setExpire(outip, ti, expired);

            std::cout << H << " " << des << " OFR " << outip << " " << IPool[outip].expire << endl;
        }
        else if (mes == "REQ") {
            if (to != H) {
                setUnused(des);
                continue;
            }

            //2.检查报文中的 IP 地址是否在地址池内，且其占用者为发送主机
            if (!(ip <= N && IPool[ip].user == des)) {
                std::cout << H << " " << des << " NAK " << ip << " 0" << endl;
                continue;
            }
            //3.
            IPool[ip].status = 3;
            //4.
            setExpire(ip, ti, expired);
            std::cout << H << " " << des << " ACK " << ip << " " << IPool[ip].expire << endl;
        }
    }
    return 0;
}