标签归档：洛谷

洛谷 同余方程

发表评论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
long long exgcd(long long a, long long b, long long &x1, long long &y1){
    if (b == 0){
        x1 = 1; y1 = 0;
        return a;
    }
    long long x, y;
    long long r = exgcd(b, a%b, x, y);
    x1 = y;
    y1 = x - a / b*y;
    return r;
}
int main(){
    ios::sync_with_stdio(false);
    long long a, b;
    cin >> a >> b;
    long long x, y;
    exgcd(a, b, x, y);
    cout << (x + b) % b;

}

做题做的心力憔悴
20180807更新：
exgcd证明过程参见：https://renjikai.com/cpp-number-theory/

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll d = exgcd(b, a%b, y, x);
    y -= a / b * x;
    return d;
}
int main() {
    ll a, b, x, y;
    cin >> a >> b;
    exgcd(a, b, x, y);
    cout << (x%b + b) % b;
}

洛谷 机器翻译

发表评论

题号：1540

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
#include<bits/stdc++.h>
using namespace std;
int m, n;
int head = 0, tail = 0;
int arr[105];
int cnt;
int main(){
    ios::sync_with_stdio(false);
    cin >> m >> n;
    m++;
    for (int i = 0; i < m; i++){
        arr[i] = -1;
    }
    for (int i = 1; i <= n; i++){
        int word;
        cin >> word;
        bool flag = false;
        for (int i = head; i != tail; i = (i + 1) % m){
            if (arr[i] == word){
                flag = true;
                break;
            }
        }
        if (!flag){
            if (head == (tail + 1) % m)head = (head + 1) % m;
            cnt++;
            arr[tail] = word;
            tail = (tail + 1) % m;
        }
    }
    cout << cnt;
}

洛谷 【模板】最近公共祖先（LCA）

发表评论

调了半天才调出来的东西啊……233，在写tarjan的循环时写错了，把_v_ask写成了_v，太容易写错了，一定要多加注意，这个模版还需要练习，线段树也是。。
Tarjan::

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
#include<bits/stdc++.h>
#define MAXN 1000005
#define MAXM 1000005
#define EdgeLoop(e,node) for(int e=_first[node];e!=-1;e=_next[e])
#define EdgeAskLoop(e,node) for(int e=_first_ask[node];e!=-1;e=_next_ask[e])
int n, m, s;
int _father[MAXN];
int graph_m_ptr = 0, graph_m_ptr_ask = 0;
int _u[MAXN], _v[MAXN], _next[MAXN], _first[MAXN];
bool _visited[MAXN];
int _u_ask[MAXN], _v_ask[MAXN], _next_ask[MAXN], _first_ask[MAXN];
int _ans[MAXM];
int _find(int x){
    if (_father[x] == x)return x;
    return _father[x] = _find(_father[x]);
}
void _merge(int x, int y){//merge y branch to x branch
    _father[_find(x)] = _find(y);
}
void insert_edge(int s, int t){
    _u[graph_m_ptr] = s;
    _v[graph_m_ptr] = t;
    _next[graph_m_ptr] = _first[s];
    _first[s] = graph_m_ptr;
    graph_m_ptr++;
}
void insert_edge_ask(int s, int t){
    _u_ask[graph_m_ptr_ask] = s;
    _v_ask[graph_m_ptr_ask] = t;
    _next_ask[graph_m_ptr_ask] = _first_ask[s];
    _first_ask[s] = graph_m_ptr_ask;
    graph_m_ptr_ask++;
}
void tarjan(int u){
    _visited[u] = true;
    EdgeLoop(e, u){
        if (!_visited[_v[e]]){
            tarjan(_v[e]);
            _merge(_v[e],u);
        }
    }
    EdgeAskLoop(e, u){
        if (_visited[_v_ask[e]]){
            _ans[e/2] = _find(_v_ask[e]);
        }
    }
}
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++){
        _father[i] = i;
    }
    memset(_first, -1, sizeof(_first));
    memset(_first_ask, -1, sizeof(_first_ask));
    for (int i = 1; i <= n - 1; i++){
        int x, y;
        cin >> x >> y;
        insert_edge(x, y);
        insert_edge(y, x);
    }
    for (int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        insert_edge_ask(a, b);
        insert_edge_ask(b, a);
    }
    tarjan(s);
    for (int i = 0; i < m; i++){
        cout << _ans[i] << endl;
    }
}

树上倍增：

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
#include<bits/stdc++.h>
using namespace std;
int edge_ptr = 0;
struct edge{
    int v;
    int next;
}edges[1000005];
int head[500005];
int n, m, s;
int father[500005][25],depth[500005];
bool visited[500005];
inline void insert_edge(int s,int t){
    edge_ptr++;
    edges[edge_ptr].v = t;
    edges[edge_ptr].next = head[s];
    head[s] = edge_ptr;
}
inline void dfs(int u){
    visited[u] = true;
    for (int i = 1, len = 1; len <= depth[u]; i++, len <<= 1){
        father[u][i] = father[father[u][i - 1]][i - 1];
    }
    for (int e = head[u]; e != -1;e=edges[e].next){
        if (!visited[edges[e].v]){
            depth[edges[e].v] = depth[u] + 1;
            father[edges[e].v][0] = u;
            dfs(edges[e].v);
        }
    }
}
inline int query(int x, int y){
    if (depth[x] > depth[y])swap(x,y);
    int diff = depth[y] - depth[x];
    for (int i = 0, two = 1; diff != 0; two <<= 1, i++){
        if (diff&two){
            y = father[y][i];
            diff -= two;
        }
    }
    if (x == y)return x;
    for (int i = log2(depth[x]); i >= 0; i--){
        if (father[x][i] != father[y][i]){
            x = father[x][i];
            y = father[y][i];
        }
    }
    return father[x][0];
}
int main(){
    ios::sync_with_stdio(false);
    memset(head, -1, sizeof(head));
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++){
        int x, y;
        cin >> x >> y;
        insert_edge(x, y);
        insert_edge(y, x);
    }
    dfs(s);
    for (int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        cout << query(x, y) << endl;
    }
}

洛谷 【模板】线段树 1

发表评论

题号：P3372

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cassert>
#include<vector>
#include<list>
#include<stack>
#include<queue>
struct node{
    long long value;
    long long lazymark;
}segment_tree[400005];
void build(int root, long long * arr, int start, int end){
    segment_tree[root].lazymark = 0;
    if (start == end){
        segment_tree[root].value = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(root * 2 + 1, arr, start, mid);
    build(root * 2 + 2, arr, mid + 1, end);
    segment_tree[root].value = segment_tree[root * 2 + 1].value + segment_tree[root * 2 + 2].value;
}
void pushdown(int root,int start,int end){
    if (segment_tree[root].lazymark == 0)return;
    int mid = (start + end) / 2;
    segment_tree[root * 2 + 1].lazymark += segment_tree[root].lazymark;
    segment_tree[root * 2 + 2].lazymark += segment_tree[root].lazymark;
    segment_tree[root * 2 + 1].value += segment_tree[root].lazymark*(mid - start + 1);
    segment_tree[root * 2 + 2].value += segment_tree[root].lazymark*(end - mid);
    segment_tree[root].lazymark = 0;
}
long long query(int root, int cstart, int cend, int qstart, int qend){
    if (qstart > cend || qend < cstart)return 0;
    if (qstart <= cstart&&cend <= qend)return segment_tree[root].value;
    pushdown(root,cstart,cend);
    int cmid = (cstart + cend) / 2;
    return query(root * 2 + 1, cstart, cmid, qstart, qend) + query(root * 2 + 2, cmid + 1, cend, qstart, qend);
}
void update(int root, int cstart, int cend, int ustart, int uend, long long addvalue){
    if (cend < ustart || uend < cstart)return;
    if (ustart <= cstart&&cend <= uend){
        segment_tree[root].value += addvalue*(cend - cstart + 1);
        segment_tree[root].lazymark += addvalue;
        return;
    }
    pushdown(root,cstart,cend);
    int cmid = (cstart + cend) / 2;
    update(root * 2 + 1, cstart, cmid, ustart, uend, addvalue);
    update(root * 2 + 2, cmid + 1, cend, ustart, uend, addvalue);
    segment_tree[root].value = segment_tree[root * 2 + 1].value + segment_tree[root * 2 + 2].value;
}

using namespace std;
int n, m;
long long arr[100005];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    build(1, arr, 1, n);
    while (m--){
        int op;
        cin >> op;
        if (op == 1){
            int x, y;
            long long z;
            cin >> x >> y >> z;
            update(1, 1, n, x, y, z);
        }
        else{//op==2
            int x, y;
            cin >> x >> y;
            cout << query(1, 1, n, x, y) << endl;
        }
    }
}

zcysky标程：

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
#include<bits/stdc++.h>
const int N=100005;
typedef long long ll;
using namespace std;
int a[N],n,m;
inline ll read(){
    ll f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
ll sumv[N<<2],addv[N<<2];
#define lson (o<<1)
#define rson (o<<1|1)
inline void pushup(int o){sumv[o]=sumv[lson]+sumv[rson];}
inline void pushdown(int o,int l,int r){
    if(!addv[o])return;
    ll tag=addv[o];addv[o]=0;int mid=(l+r)>>1;
    addv[lson]+=tag;addv[rson]+=tag;
    sumv[lson]+=tag*1LL*(mid-l+1);sumv[rson]+=tag*1LL*(r-mid);
}
inline void build(int o,int l,int r){
    if(l==r){sumv[o]=a[l];return;}
    int mid=(l+r)>>1;
    build(lson,l,mid);build(rson,mid+1,r);
    pushup(o);
}
inline void optadd(int o,int l,int r,int ql,int qr,ll v){
    if(ql<=l&&r<=qr){sumv[o]+=v*1LL*(r-l+1);addv[o]+=v;return;}
    int mid=(l+r)>>1;pushdown(o,l,r);
    if(ql<=mid)optadd(lson,l,mid,ql,qr,v);
    if(qr>mid)optadd(rson,mid+1,r,ql,qr,v);
    pushup(o);
}
inline ll querysum(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return sumv[o];
    pushdown(o,l,r);
    int mid=(l+r)>>1;ll ans=0;
    if(ql<=mid)ans+=querysum(lson,l,mid,ql,qr);
    if(qr>mid)ans+=querysum(rson,mid+1,r,ql,qr);
    return ans;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    while(m--){
        int opt=read(),l=read(),r=read();
        if(opt==1){
            ll k=read();optadd(1,1,n,l,r,k);
        }
        else printf("%lld\n",querysum(1,1,n,l,r));
    }
}

20180816更新：

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
#include<iostream>
using namespace std;

struct segmentTree{
    typedef long long ll;
    const static ll MAX=100000;
    ll v[4*MAX],m[4*MAX];
    inline static ll lson(ll r){return r*2+1;}
    inline static ll rson(ll r){return r*2+2;}
    void build(ll r,ll * a,ll s,ll e){
                m[r]=0;
                if(s==e){v[r]=a[s];return;}
                ll md=(s+e)>>1;
        build(lson(r),a,s,md);
        build(rson(r),a,md+1,e);
        v[r]=v[lson(r)]+v[rson(r)];
        }
    void pushDown(ll r,ll s,ll e){
        if(m[r]==0)return;
        ll md=(s+e)>>1;
        m[lson(r)]+=m[r];
        m[rson(r)]+=m[r];
        v[lson(r)]+=m[r]*(md-s+1);
        v[rson(r)]+=m[r]*(e-md);
        m[r]=0;
    }
    ll query(ll r,ll cs, ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r];
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)/2;
        return query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe);
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv){
        if(ce<us||ue<cs)return;
        if(us<=cs&&ce<=ue){v[r]+=addv*(ce-cs+1);m[r]+=addv;return;}
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv);
        update(rson(r),cmd+1,ce,us,ue,addv);
        v[r]=v[lson(r)]+v[rson(r)];
    }
}ST;
typedef long long ll;
ll n,m;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        int op,x,y,k;
        cin>>op;
        if(op==1){
            cin>>x>>y>>k;
            ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)<<endl;
        }
    }
}

洛谷 车站分级

发表评论

题号：P1983
算法标签：拓扑排序
洛谷题解地址：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1983
参考题解：作者: chenshaoqian 更新时间: 2016-09-25 21:08
作者: mangoyang 更新时间: 2016-09-24 17:20

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<list>
#include<stack>
using namespace std;
#define virtual_point_start 1000
int n, m;
int s[1005];
int virtual_point_ptr = virtual_point_start;
int indegree[3000];
int pass[1005][1005];
int path_dis[3000];
list<int> edge[3000];
vector<int> t_edge_to;
stack<int> cur_level;
bool execute(){
    while (!cur_level.empty())cur_level.pop();
    for (int i = 1; i <= n; i++){
        if (indegree[i] == 0){
            cur_level.push(i);
            indegree[i] = -1;
        }
    }
    for (int i = 1001; i <= virtual_point_ptr; i++){
        if (indegree[i] == 0){
            cur_level.push(i);
            indegree[i] = -1;
        }
    }
    if (cur_level.empty())return false;
    while (!cur_level.empty()){
        int cur = cur_level.top();
        cur_level.pop();
        for (list<int>::iterator iter = edge[cur].begin(); iter != edge[cur].end(); iter++){
            indegree[*iter]--;
            int point_dis = (cur <= 1000);
            path_dis[*iter] = max(path_dis[*iter],path_dis[cur] + point_dis);
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)cin >> pass[i][j];
        t_edge_to.clear();
        int ptr = 1;
        for (int j = pass[i][1]; j <= pass[i][s[i]]; j++){
            if (pass[i][ptr] == j)ptr++;
            else t_edge_to.push_back(j);
        }
        virtual_point_ptr++;
        for (vector<int>::iterator iter = t_edge_to.begin(); iter != t_edge_to.end(); iter++){
            edge[virtual_point_ptr].push_back(*iter);
            indegree[*iter]++;
        }
        for (int se = 1; se <= s[i]; se++){
            edge[pass[i][se]].push_back(virtual_point_ptr);
            indegree[virtual_point_ptr]++;
        }
    }
    while (execute());
    int ans = 0;
    for (int i = 1; i <= n; i++){
        ans = max(ans, path_dis[i]);
    }
    cout << ans+1;
}

20180814更新：
题解：https://www.luogu.org/blog/24212/solution-p1983
主要是借鉴了一个开一个二维数组判断边是否加重的问题。
还有一个最重要的就是“由停车的站向不停车的站连边”问题，总是考虑不到。

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
#include<iostream>
#include<vector>
using namespace std;
int n,m;
bool visited[1002][1002];
int inDegree[1002],grades[1002];
vector<int> edges[1002];
vector<int> railStation;
vector<int> unStopStation;
vector<int> curGrade;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        railStation.clear();
        unStopStation.clear();
        int num;
        cin>>num;
        for(int j=1;j<=num;j++){
            int t;
            cin>>t;
            railStation.push_back(t);
        }
        for(int j=0;j<railStation.size()-1;j++){
            for(int k=railStation[j]+1;k<railStation[j+1];k++){
                unStopStation.push_back(k);
            }
        }
        for(int j=0;j<railStation.size();j++){
            for(int k=0;k<unStopStation.size();k++){
                if(visited[railStation[j]][unStopStation[k]])continue;
                visited[railStation[j]][unStopStation[k]]=true;
                edges[railStation[j]].push_back(unStopStation[k]);
                inDegree[unStopStation[k]]++;
            }
        }
    }
    int maxV=0;
    do{
        curGrade.clear();
        for(int i=1;i<=n;i++){
            if(inDegree[i]==0){
                curGrade.push_back(i);
                inDegree[i]--;
            }
        }
        for(int i=0;i<curGrade.size();i++){
            grades[curGrade[i]]++;
            for(int j=0;j<edges[curGrade[i]].size();j++){
                grades[edges[curGrade[i]][j]]=max(grades[edges[curGrade[i]][j]],grades[curGrade[i]]);
                inDegree[edges[curGrade[i]][j]]--;
            }
            maxV=max(maxV,grades[curGrade[i]]);
        }
    }while(curGrade.size());
    cout<<maxV;
}

洛谷 海底高铁

发表评论

题号：P3406
把数据类型都开成long long，不然等着丢分？？

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<algorithm>
using namespace std;
int n, m;
long long track_dif[100005], track[100005];
long long P[100005];
long long A[100005], B[100005], C[100005];
long long cost;
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> P[i];
    }
    for (int i = 1; i <= n - 1; i++){
        cin >> A[i] >> B[i] >> C[i];
    }
    for (int i = 1; i <= m - 1; i++){
        int l = min(P[i], P[i + 1]), r = max(P[i], P[i + 1]);
        track_dif[l]++;
        track_dif[r]--;
    }
    for (int i = 1; i <= n - 1; i++){
        track[i] = track[i - 1] + track_dif[i];
    }
    for (int i = 1; i <= n - 1; i++){
        cost += min(track[i] * A[i], C[i] + track[i] * B[i]);
    }
    cout << cost;
}

洛谷10月月赛R2·浴谷八连测R3 -Chtholly- Chtholly Nota Seniorious

发表评论

洛谷题号：3933
乱搞、二分答案+贪心，根本想不出来，打暴力30分……

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
int n, m;
int arr[2005][2005];
int arr_rotate[2005][2005];
int pos[2005];
int minnum = 2e9, maxnum = 0;
bool check(int value){
    int limit = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (arr[i][j] >minnum+value)limit = max(limit, j + 1);
        }
        for (int j = 1; j <= m; j++){
            if (maxnum - value > arr[i][j])if (j < limit)return false;
        }
    }
    return true;
}
/*check问题搞不懂可以仔细阅读T2题解
check的等效写法：
bool check(int value){
    int limit = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (arr[i][j] < maxnum - value)limit = max(limit, j + 1);
        }
        for (int j = 1; j <= m; j++){
            if (minnum + value < arr[i][j])if (j < limit)return false;
        }
    }
    return true;
}
*/
void rotate90degrees(){
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            arr_rotate[j][n-i+1] = arr[i][j];
        }
    }
    memcpy(arr, arr_rotate, sizeof(arr));
    swap(n, m);
}

int solve(){
    int low = 0, high = maxnum - minnum,mid;
    while (low < high){
        mid = (low + high) / 2;
        if (check(mid)){
            high= mid;
        }
        else{
            low = mid + 1;
        }
    }
    return low;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> arr[i][j];
            maxnum = max(maxnum,arr[i][j]);
            minnum = min(minnum,arr[i][j]);
        }
    }
    int re = 2e9;
    for (int i = 1; i <= 4; i++){
        re = min(re, solve());
        rotate90degrees();
    }
    cout << re;
    return 0;
}

洛谷10月月赛R2·浴谷八连测R3 -Chtholly- 浮游大陆的68号岛

发表评论

洛谷题号：3932
一个前缀和的破题改了两个钟头，真是罪过。。。
借鉴了xsun2001同学的思路……在此表示感谢。。。
原来xsun2001同学代码中有可能存在的两点错误：第一个，有可能错在read函数里，读入进来的是int。第二，中间的所有计算过程全部需要取模。我把这两点改好之后就没问题了。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
#define MOD 19260817
long long n, m;
long long dis[200005], goods[200005];
long long prefixsum_dis[200005], prefixsum_goods[200005], prefixsum_cost[200005];
//从1到i点的距离/物品数/距离*物品数
#define LeftDis(l,r,x) ((prefixsum_cost[r] - prefixsum_cost[l - 1] + MOD)% MOD - (prefixsum_dis[x] * (prefixsum_goods[r] - prefixsum_goods[l - 1] + MOD) % MOD) + MOD) % MOD
#define RightDis(l,r,x) ((prefixsum_dis[x] * (prefixsum_goods[r] - prefixsum_goods[l - 1] + MOD) % MOD) - (prefixsum_cost[r] - prefixsum_cost[l - 1] + MOD) % MOD +MOD ) % MOD
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 2; i <= n; i++){
        cin >> dis[i];
        dis[i] %= MOD;
    }
    for (int i = 1; i <= n; i++){
        cin >> goods[i];
        goods[i] %= MOD;
    }
    for (int i = 1; i <= n; i++){
        prefixsum_dis[i] = (prefixsum_dis[i - 1] + dis[i]) % MOD;
        prefixsum_goods[i] = (prefixsum_goods[i - 1] + goods[i] % MOD) % MOD;
        prefixsum_cost[i] = (prefixsum_cost[i - 1] + prefixsum_dis[i] * goods[i] % MOD) % MOD;
    }
    for (long long i = 1; i <= m; i++){
        long long result = 0;
        long long x, l, r;
        cin >> x >> l >> r;
        if (l >= x){
            result += LeftDis(l,r,x);
        }
        else if (r <= x){
            result += RightDis(l,r,x);
        }
        else{
            result += LeftDis(x + 1, r, x);
            result += RightDis(l, x - 1, x);
        }

        cout << result%MOD << endl;
    }
    return 0;
}

题解地址：
洛谷月赛R2训练营R3

洛谷 计算系数

发表评论

题号：P1313
大晚上的刷杨辉三角………………

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
#define MOD 10007
long long arr[1005][1005];
long long a, b, k, n, m;
long long quickpow(long long x, long long y){
    if (y == 0)return 1;
    long long qpsqr2 = quickpow(x, y / 2)%MOD;
    if (y % 2 == 0){
        return (qpsqr2*qpsqr2) % MOD;
    }
    else{
        return (((qpsqr2*qpsqr2) % MOD)*(x%MOD)) % MOD;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> a >> b >> k >> n >> m;
    for (int i = 0; i <= 1000; i++){
        arr[0][i] = 1;
        arr[i][i] = 1;
    }
    for (int i = 1; i <= 1000; i++){
        for (int j = 1; j < i; j++){
            arr[j][i] = (arr[j][i - 1] % MOD + arr[j - 1][i - 1] % MOD) % MOD;
        }
    }
    long long ans = arr[n][k];
    ans = (ans*quickpow(a, n)) % MOD;
    ans = (ans*quickpow(b, m)) % MOD;
    cout << ans;
    return 0;
}

20180808更新：
不用杨辉三角啦！因为我会乘法逆元啦！！！哈哈

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
#define MOD 10007
ll a,b,k,n,m;
//C(min(n,m),k)*b^m*a^n
ll quickpow(ll a, ll b) {
    if (b == 0)return 1;
    ll re = quickpow(a, b / 2) % MOD;
    re = (re*re) % MOD;
    if (b % 2 == 1)re *= a % MOD;
    return re % MOD;
}
ll inv(ll x) {
    return quickpow(x, MOD - 2) % MOD;
}
int main() {
    cin >> a >> b >> k >> n >> m;
    ll re = (quickpow(a, n)*quickpow(b, m)) % MOD;
    ll cU = 1;
    for (ll i = k; i >= k - min(n, m) + 1; i--) {
        cU *= i % MOD;
        cU %= MOD;
    }
    ll cD = 1;
    for (ll i = 1; i <= min(n, m); i++) {
        cD *= i % MOD;
        cD %= MOD;
    }
    re = ((re * cU) % MOD*inv(cD)) % MOD;
    cout << re;
}

洛谷 守望者的逃离

发表评论

洛谷题号：P1095
参考题解：作者: 究极龙骑士 更新时间: 2017-07-11 22:44 https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1095

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
int m, s, t;
int main(){
    ios::sync_with_stdio(false);
    cin >> m >> s >> t;
    int s1 = 0, s2 = 0;//s1跑步,s2瞬间移动
    for (int time = 1; time <= t; time++){
        s1 += 17;
        if (m >= 10){
            m -= 10;
            s2 += 60;
        }
        else{
            m += 4;
        }
        if (s1 < s2)s1 = s2;
        if (s1> s){
            cout << "Yes" << endl << time << endl;
            return 0;
        }
    }
    cout << "No" << endl << s1 << endl;
    return 0;
}