Diposting di

比赛流水账

开始J题 看懂题意都知道要么是2 要么是3 然后直接判断素数就行，结果因为时间卡得紧 用在for 循环里面用ll进行运算复杂度太大。 （这里我tle了两次，原因是有两点，这判断本身就是sqrt（n）的 挺慢，但是当时比赛觉得这就是个签到没必要想那么长时间。就直接交了个暴力。 还有就是这里的机子和平时不一样，平时不会卡这种ll的常数。）

后面的 两题直接秒过 没意义。

这时候I题，我看了挺久，确定是自己不会做的题，让俊逸想，俊逸讲了思路，听不懂，然后去看G

G题看了一眼，想到了线段树合并，复杂度是nlogn的，然后直接上机写，同时叫书浩 推最后的答案公式。

写完线段树合并 让sh讲答案公式，没讲懂，但是听出是个贪心，然后自己想了个贪心写上去。RE，一直RE 这RE了两小时。（原因是线段树合并在这种情况下时间空间复杂度都会退化）

最后一小时 想换种方法做（倒着推贡献），然后套上最后算答案的方法，wa。这时候比赛结束。

（wa 是因为最后算答案的方法是错误的。不能贪心。因为交换次数无限。）

个人总结

做签到题的时候 没办法，我没预料到这种情况。 没针对浙大的出题研究卡常。

G题演了，线段树合并 一直不相信自己的复杂度 却又盲目相信，其实交了第一发就已经有预感到了，但是没想到空间也会退化。

团队总结

队伍交流落后。

我基本听不懂sh和ljy的思路。两位表达能力堪忧。 解决方法只能是多交流，之前写的博客怎么全没作用了。不理解。

比赛节奏差，被拖死了，客观来看 这场能做的只有这五题 除去这五题 基本不可能开题了，如果能有两小时以上的充分时间，最后一题我也是可以做的。

Diposting di 

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
i=0 pre=0000 nex=0001
i=0 pre=0010 nex=0011
i=0 pre=0100 nex=0101
i=0 pre=0110 nex=0111
i=0 pre=1000 nex=1001
i=0 pre=1010 nex=1011
i=0 pre=1100 nex=1101
i=0 pre=1110 nex=1111
i=1 pre=0000 nex=0010
i=1 pre=0001 nex=0011
i=1 pre=0100 nex=0110
i=1 pre=0101 nex=0111
i=1 pre=1000 nex=1010
i=1 pre=1001 nex=1011
i=1 pre=1100 nex=1110
i=1 pre=1101 nex=1111
i=2 pre=0000 nex=0100
i=2 pre=0001 nex=0101
i=2 pre=0010 nex=0110
i=2 pre=0011 nex=0111
i=2 pre=1000 nex=1100
i=2 pre=1001 nex=1101
i=2 pre=1010 nex=1110
i=2 pre=1011 nex=1111
i=3 pre=0000 nex=1000
i=3 pre=0001 nex=1001
i=3 pre=0010 nex=1010
i=3 pre=0011 nex=1011
i=3 pre=0100 nex=1100
i=3 pre=0101 nex=1101
i=3 pre=0110 nex=1110
i=3 pre=0111 nex=1111
i=0000
i=0001 0000
i=0010 0000
i=0011 0010 0001
i=0100 0000
i=0101 0100 0001
i=0110 0100 0010
i=0111 0110 0101 0011
i=1000 0000
i=1001 1000 0001
i=1010 1000 0010
i=1011 1010 1001 0011
i=1100 1000 0100
i=1101 1100 1001 0101
i=1110 1100 1010 0110
i=1111 1110 1101 1011 0111

Process returned 0 (0x0)   execution time : 0.067 s
Press any key to continue.
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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+50;
typedef long long ll;
const ll mod=1e9+7;

char s[maxn];
int dp[(1<<21)+50];
bool ok[(1<<21)+50];
int cal(int x){
    if(x==0)return 0;
    return x%2+cal(x/2);
}
vector<int>v[maxn];

int main(){
    std::ios::sync_with_stdio(false);
    for(int i=0;i<4;i++){
        for(int j=0;j<(1<<4);j++){
            if((j&(1<<i))==0){
                bitset<4> a(j);
                cout<<"i="<<i<<" pre="<<a<<" nex=";
                a.set(i);
                cout<<a.set(i)<<endl;
                v[j|(1<<i)].push_back(j);
                dp[j|(1<<i)]=max(dp[j|(1<<i)],dp[j]);
            }
        }
    }
    for(int i=0;i<(1<<4);i++){
        bitset<4> a(i);
        cout<<"i="<<a<<" ";
        for(auto j:v[i]){
            bitset<4> b(j);
            cout<<b<<" ";
        }
        cout<<endl;
    }
    return 0;
}

Diposting di

B.Broken Watch

题解

先不考虑长度 长度不会影响会不会过中心。

如果长度相同 $C_{n}^{3}$ 再减去不符合的再同一侧的。

再根据长度关系乘$C_{3}^{2}$ 或$C_3^1$

C.Tree (暴力)

题意

给你一棵树，树中有黑点和白点，让你选出m个黑点使得他们的最长距离最短。输出最长距离。

思路

直接枚举两个黑点，其他点到这两个黑点的距离的最大值不能超过他们之间的距离。

E - Fishermen (差分)

题意

签到不讲了。

Inversion （dp）

题解

转化题意就是求分段的组合个数，根据连线，肯定前面会和后面连接，

$dp[i]$表示第i个元素作为最后一个 那么它的答案就是由前面没有和它连线的$dp[k]$ 转移过来，同时因为要包含所有其他的元素，所以还需要他们中间的所有元素要么和i连线或者k连线。

K - Points and Rectangles (cdq 分治)

题意

每次添加矩阵和点 ，每次添加都要查询 所有矩阵中的点的个数

思路

求矩阵中点个数，是模板，求点在多少矩阵中，也可以差分，求多少个矩阵的左下角在这个点的左下边。

Diposting di

该图涉及的链为

$rt-u\\rt-u-a\\rt-u-b\\rt-v\\rt-v-c\\rt-v-d​$

还有

$a-u-rt-u-b\\c-v-rt-v-d$

发现后面两个是不符合题意的

于是我们要删去这两个

于是我们进来rt-u这里

获得这两个链 于是我们减去这两个链

$rt-u-a\\ rt-u-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
int dep[maxn],a[maxn];
void dfsdeep(int u,int fa){
    a[++a[0]]=dep[u];
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(vis[v]||v==fa)continue;
        dep[v]=dep[u]+Len[i];
        dfsdeep(v,u);
    }
}
void cal(int u,int now,int op){
    dep[u]=now,a[0]=0;
    dfsdeep(u,0);
    for(int i=1;i<=a[0];i++){
        for(int j=1;j<=a[0];j++){
            num[a[i]+a[j]]+=op;
        }
    }
}
void solve(int u){
    vis[u]=1;
    cal(u,0,1);
    for(int i=Laxt[u];i;i=Next[i]){
        int v=To[i];
        if(vis[v])continue;
        cal(v,Len[i],-1);
        sum=sz[v];
        root=0;findroot(v,0);
        solve(root);
    }
}

当然 还有一种不需要容斥的做法，我们发现 唯一的区别就是$u,v$ 重复了。

于是我们可以通过先进入$u$然后再计算u的所有答案。

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
int a[N], dis[10000003];
int md[N], MK, cnt;
void getdis(int now, int pre, int di) {
	if (di > MK)return ;
	md[++cnt] = di;
	for (auto k : v[now]) {
		if (vis[k.fi] || k.fi == pre)continue;
		getdis(k.fi, now, di + k.se);
	}
}
int qa[N], tmp;
void get(int now, int pre) {
	dis[0] = 1;
	for (auto k : v[now]) {
		if (k.fi == pre || vis[k.fi])continue;
		cnt = 0;
		getdis(k.fi, now, k.se);
		for (int i = 1; i <= cnt; ++i) {
			for (int j = 1; j <= m; j++) {
				if (q[j] >= md[i])a[j] |= dis[q[j] - md[i]];
			}
		}
		for (int i = 1; i <= cnt; i++)dis[md[i]] = 1, qa[++tmp] = md[i];
	}
}
void dfs(int now) {
	vis[now] = 1;
	tmp = 0;
	get(now, 0);
	for (int i = 1; i <= tmp; i++)dis[qa[i]] = 0;
	for (auto k : v[now]) {
		if (vis[k.fi])continue;
		rt = 0;
		n = sz[k.fi];
		root(k.fi, 0);
		dfs(rt);
	}
	return ;
}
————————————————
版权声明：本文为CSDN博主「pubgoso」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_40655981/article/details/100886381

Diposting di

传送门

题意

给出一个长度为$n$字符串$s$， $m$次询问，每次问你字符串$s$区间内的字符串$l,r$第$k$次出现的位置。

思路

比赛的时候一眼就知道是$sa$但是对于$sa$实在不喜欢，于是比赛的时候整场用$sam$硬怼。已经想到了用主席树记录$endpos$位置，然后从后往前推过去，但是比赛时还不会在$sam$上玩权值线段树合并，赛后学习了一下。

首先，这题我们可以在$sam$上的每个新开节点上存储这个节点是在原串的那个位置是把。

然后对于一个串$i​$他的$father​$肯定是他的$后缀​$ 所以他的$endpos​$肯定也是他$father​$的$endpos​$

同时一个$father$不仅仅只有$i$这个儿子 所以$father$的继承是从很多儿子那边的来的，于是我们需要搞笑处理继承效果，这里用到了权值线段树合并,线段树下标是$endpos$在$s$的位置。

这样我们就可以通过找到一个点而得出这个点所有的$endpos$ ，也可以很快的在权值线段树中找到第$k$大的$endpos $。但是$Q$次查询每次都可能用一个长度$1e5$的串进入$sam$中找这个点的位置，于是我们考虑离线操作，将询问按照$r$排序。但是我们找到了一个点之后可能这个长度太大了，于是我们需要跳到这个点的$father$ 知道这个点的长度刚好大于等于我们需要的长度，这样答案才完整。因为$father$的长度是单调的，于是我们可以考虑用树上倍增 快速找到合适的$father$。

于是这题就愉快的结束了。真爽啊。debug都不需要。

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=5e5+50;
int ls[maxn*80],rs[maxn*80],rt[maxn*80],sum[maxn*80],cnt;
void update(int &o,int l,int r,int pos){
    if(!o)o=++cnt;
    if(l==r){
        sum[o]++;return;
    }
    int mid=(l+r)/2;
    if(pos<=mid)update(ls[o],l,mid,pos);
    else update(rs[o],mid+1,r,pos);
    sum[o]=sum[ls[o]]+sum[rs[o]];
}
int merger(int o,int pre,int l,int r){
    if(!o)return pre;if(!pre)return o;
    int k=++cnt;
    if(l==r){
        sum[k]=sum[o]+sum[pre];
        return k;
    }int mid=(l+r)/2;
    ls[k]=merger(ls[o],ls[pre],l,mid);
    rs[k]=merger(rs[o],rs[pre],mid+1,r);
    sum[k]=sum[ls[k]]+sum[rs[k]];
    return k;
}
int query(int o,int l,int r,int k){
    if(sum[o]<k)return -1;
    if(l==r)return l;
    int mid=(l+r)/2;
    if(sum[ls[o]]>=k)return query(ls[o],l,mid,k);
    else return query(rs[o],mid+1,r,k-sum[ls[o]]);
}
struct Q{
    int l,r,k,id;
    bool operator<(const Q &o)const{
        return r<o.r;
    }
}my[maxn];
int n;
char s[maxn];
int ans[maxn];
struct SAM{
    int fa[maxn],ch[maxn][26],maxlen[maxn],tot,last;
    int sz[maxn],a[maxn],b[maxn];
    void init(){
        cnt=0;
        fill(rt,rt+n*80,0);
        fill(ls,ls+n*80,0);
        fill(rs,rs+n*80,0);
        fill(sum,sum+n*80,0);
        tot=last=1;maxlen[1]=fa[1]=0;
        memset(ch[1],0,sizeof(ch[1]));
    }
    void add(int x,int id){
        int np=++tot,p=last;last=np;update(rt[np],1,n,id);
        maxlen[np]=maxlen[p]+1;sz[np]=1;
        memset(ch[np],0,sizeof(ch[np]));
        while(p&&!ch[p][x])ch[p][x]=np,p=fa[p];
        if(!p)fa[np]=1;
        else{
            int q=ch[p][x];
            if(maxlen[q]==maxlen[p]+1)fa[np]=q;
            else{
                int nq=++tot;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                fa[nq]=fa[q],fa[np]=fa[q]=nq;
                maxlen[nq]=maxlen[p]+1;
                while(p&&ch[p][x]==q)ch[p][x]=nq,p=fa[p];
            }
        }
    }
    int pa[maxn][25];
    void Sort(){///拓扑排序 得到每个集合里的串出现次数
        for(int i=1;i<=tot;i++)a[i]=0;
        for(int i=1;i<=tot;i++)a[maxlen[i]]++;
        for(int i=1;i<=tot;i++)a[i]+=a[i-1];
        for(int i=1;i<=tot;i++)b[a[maxlen[i]]--]=i;
        for(int i=tot;i;i--)sz[fa[b[i]]]+=sz[b[i]];
        for(int i=tot;i;i--){
            int k=b[i];
            pa[k][0]=fa[k];
            rt[fa[k]]=merger(rt[fa[k]],rt[k],1,n);
        }
        for(int i=1;i<=20;i++){
            for(int j=1;j<=tot;j++){
                int v=pa[j][i-1];
                pa[j][i]=pa[v][i-1];
            }
        }
    }
    int go(int id,int len){
        for(int i=20;i>=0;i--){
            if(maxlen[pa[id][i]]>=len)id=pa[id][i];
        }
        return id;
    }
    int m;
    void slove(){
        for(int i=1;i<=m;i++){
            cin>>my[i].l>>my[i].r>>my[i].k;
            my[i].id=i;
        }
        sort(my+1,my+1+m);
        int now=1;
        int tail=1;
        for(int i=1;i<=n;i++){
            int x=s[i]-'a';
            now=ch[now][x];
            while(tail<=m&&my[tail].r==i){
                int len=my[tail].r-my[tail].l+1;
                int where=go(now,len);
                int aa=query(rt[where],1,n,my[tail].k);
                if(aa==-1)ans[my[tail].id]=-1;
                else{
                    ans[my[tail].id]=aa-len+1;
                }
                tail++;
            }
        }
        for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
    }
}S;
int main()
{
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        cin>>n;cin>>S.m;
        cin>>s+1;
        n=strlen(s+1);S.init();
        for(int i=1;i<=n;i++)S.add(s[i]-'a',i);
        S.Sort();
        S.slove();
    }
    return 0;
}

Diposting di

A.Jumping Buildings (单调栈)

思路

对于每个位置通过单调栈可以得出右边第一个比他高的位置。复杂度$O(n)$

代码

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=5e5+50;
 
int h[maxn];
int R[maxn];
 
int main()
{
    std::ios::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    stack<int>st;
    for(int i=n;i;i--){
        while(!st.empty()&&h[i]>=h[st.top()]){
            st.pop();
        }
        if(!st.empty())R[i]=st.top()-i-1;
        else
            R[i]=n-i;
        st.push(i);
    }
    for(int i=1;i<=n;i++)cout<<min(h[i],R[i])<<" ";
    return 0;
}

B.Divples （因数分解）

思路

很简单的签到了把。直接枚举a的因子判断是否是b的倍数即可 复杂度$O(sqrt(n))$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=5e5+50;
 
int main()
{
    std::ios::sync_with_stdio(false);
    ll a,b;
    cin>>a>>b;
    vector<ll>v;
    for(ll i=1;i*i<=a;i++){
        if(a%i==0){
            if(i%b==0)v.push_back(i);
            if((i!=a/i)&&((a/i)%b)==0)v.push_back(a/i);
        }
    }
    sort(v.begin(),v.end());
    for(auto i:v)cout<<i<<" ";
    return 0;
}

C.Rectangles （离散化预处理后暴力）

思路

关键点就是中间和线上不能有点，那么我们可以考虑枚举一行的两个点，(可以知道这两个点必须是相邻的) 然后我们再在下面的几行中找是否有和这两个点可以组成矩形的点，

同时注意要保证不能矩形中间和线上出现点 复杂度$O(n^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
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<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=5e5+50;
 
pair<int,int>p[maxn];
 
vector<int>X[maxn];
 
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int>v;
    for(int i=1;i<=n;i++)cin>>p[i].first>>p[i].second,v.push_back(p[i].first),v.push_back(p[i].second);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
 
    for(int i=1;i<=n;i++){
        int x=lower_bound(v.begin(),v.end(),int(p[i].first))-v.begin()+1;
        int y=lower_bound(v.begin(),v.end(),int(p[i].second))-v.begin()+1;
        X[x].push_back(y);
    }n=v.size();
    int ans=0;
    for(int i=1;i<=n;i++)sort(X[i].begin(),X[i].end());
    for(int i=1;i<=n;i++){
        if(X[i].size()<2)continue;
        for(int j=0;j<X[i].size()-1;j++){
            int a=X[i][j],b=X[i][j+1];
            int flag=1;
            for(int j=i+1;flag&&j<=n;j++){
                if(X[j].size()==0)continue;
                int k=lower_bound(X[j].begin(),X[j].end(),a)-X[j].begin();
                if(k==X[j].size())continue;
                if(X[j][k]>b)continue;
                if(X[j][k]>a&&X[j][k]<b){
                    flag=0;break;
                }
                if(X[j].size()==1&&X[j][k]==a){
                    flag=0;continue;
                }
                if(X[j].size()==1&&X[j][k]==b){
                    flag=0;continue;
                }
                auto kk=upper_bound(X[j].begin(),X[j].end(),b)-X[j].begin();
                --kk;
                if(kk-k!=1){
                    flag=0;break;
                }
                if(X[j].size()<2)continue;
                k=lower_bound(X[j].begin(),X[j].end(),a)-X[j].begin();
                if(k<X[j].size()-1){
                    if(X[j][k]==a&&X[j][k+1]==b)ans++,flag=0;
                    else if(X[j][k]==a)flag=0;
                    else if(X[j][k]>=a&&X[j][k]<=b)flag=0;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

D.Guessing Messages (签到)

思路

直接两个指针正着做就行了 复杂度$O(max(n,m))$

代码

E Chi’s performance (简单DP)

思路

首先我们需要感性得知道放在两边的数必须是最大或者最小值(请自行证明,不难的)

但是有可能两边都方最大值会更优，所以我们就需要存储次大值。

之后我们就可以总结出，对于每一个ID 只有四个元素会有贡献，所以我们对于每一个ID只要存这四个值就行，然后我们暴力DP 每个位置前面放什么数字后面放什么数字

代码

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
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e6+50;
 
pair<ll,ll>p[maxn];
struct node{
    vector<ll>vv;
    void update(vector<ll> v){
        if(v.size()<=4)vv=v;
        else{
            vv.push_back(v[0]);
            vv.push_back(v[1]);
            vv.push_back(v[v.size()-2]);
            vv.push_back(v[v.size()-1]);
        }
    }
}my[maxn];
vector<ll>v[maxn];
ll dp[maxn][5]; /// 1 mi1, 2 mi2, 3 mx1 4 mx2;
int main()
{
    std::ios::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].first>>p[i].second;
    }
    sort(p+1,p+1+n);
    ll cnt=0,mx=0;
    for(int i=1;i<=n;i++){
        if(p[i].first>mx){
            v[++cnt].push_back(p[i].second);
            mx=p[i].first;
 
        }
        else v[cnt].push_back(p[i].second);
    }
    for(int i=1;i<=cnt;i++)sort(v[i].begin(),v[i].end());
    for(int i=1;i<=cnt;i++){
        my[i].update(v[i]);
    }
    memset(dp,0,sizeof(dp));
   // cout<<"cnt="<<cnt<<endl;
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<my[i+1].vv.size();j++){
            for(int k=0;k<my[i].vv.size();k++){
                for(int kk=0;kk<my[i].vv.size();kk++){
                    if(k==kk&&my[i].vv.size()>1)continue;
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+abs(my[i].vv[kk]-my[i+1].vv[j]));
                  //  cout<<"dp["<<i<<"]["<<j<<"]="<<dp[i][j]<<endl;
                }
            }
        }
    }
    ll ans=0;
    for(int i=0;i<=4;i++){
        ans=max(ans,dp[cnt-1][i]);
    }
    cout<<ans<<endl;
    return 0;
}

G.Log Concave Sequences （矩阵快速幂）

思路

首先手动推一下 发现后面一个字符可以填什么只会跟最后面两个字符有关系。所以我们可以考虑存储后面两个字符的状态总共有$3*3=9$种 我们假设一个简单的方法，

$dp[n][pos] $ 表示长度为N最后面两个状态为$pos$的字符串个数 那么这个答案可以直接从$dp[n-1][pos*]$ 得来，但是题目的N有$1e18​$ 所以我们考虑矩阵快速幂，矩阵快速幂的矩阵怎么推出来代码中有，请自行理解。

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>
typedef long long ll;
using namespace std;
const int maxn=1e6+50;

int f[3][3],a[3][3];
 
int go[3][3][3];
vector<pair<int,int> > v[3][3];
int b[9][9];
int bb[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
};
map<pair<int,int>,int>mp;

int main()
{
    std::ios::sync_with_stdio(false);
    int cnt=0;
    for(int i=0;i<=2;i++)for(int j=0;j<=2;j++){
        mp[{i,j}]=cnt++;
    }
    for(int i=0;i<=2;i++)for(int j=0;j<=2;j++)f[i][j]=1;
    for(int i=3;i<=3;i++){
        for(int j=0;j<=2;j++){
            for(int k=0;k<=2;k++){
                for(int kk=0;kk<=2;kk++){
                    if(j*kk<=k*k){
                        v[k][kk].push_back({j,k});
                    }
                }
            }
        }
    }
    for(int i=0;i<=2;i++){
        for(int j=0;j<=2;j++){
            for(auto o:v[i][j]){
                cout<<o.first<<" "<<o.second<<" -> "<<i<<" "<<j<<endl;
            }
        }
    }
    for(int i=0;i<=2;i++){
        for(int j=0;j<=2;j++){
            for(auto o:v[i][j]){
             //   cout<<o.first<<" "<<o.second<<" -> "<<i<<" "<<j<<endl;
                b[mp[{i,j}]][mp[{o.first,o.second}]]=1;
            }
        }
    }
    for(int i=0;i<=8;i++){
        for(int j=0;j<=8;j++){
            cout<<b[i][j]<<",";
        }
        cout<<endl;
    }
    return 0;
}

I.Left or Right? How about neither? (最短路 dij)

思路

题目相当于一个状态可以有三种状态转移

1.跳到左边

2.跳到右边

3.跳到相同的数字

如果就这样一直走的话复杂度会很爆炸，但是我们发现跳到相同的数字这个条件很特殊

可以猜到相同的数字只会跳一次，比如你现在是数字3你跳到相同的数字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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
const int oo=1e5+20;
map<int,int>mp;
 
vector<int>V[maxn];
int cnt;
bool vis[maxn];
ll value[maxn];
int a[maxn];
struct node{
    int id;
    ll value;
    bool operator<(const node &o)const{
        return value>o.value;
    }
};
int main()
{
    ll n,L,R,C;
    cin>>n>>L>>R>>C;
    int u,v;cin>>u>>v;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(mp.count(a[i])==0)mp[a[i]]=++cnt;
        V[mp[a[i]]].push_back(i);
    }
    priority_queue<node>Q;
    fill(value,value+oo,1000000000000000000LL);
    value[u]=0;
    Q.push({u,0});
    while(!Q.empty()){
        node now=Q.top();
        Q.pop();
        int id=now.id;
        ll v=now.value;
        if(id-1>=1&&value[id-1]>v+L){
            value[id-1]=v+L;
            Q.push({id-1,v+L});
        }
        if(id+1<=n&&value[id+1]>v+R){
            value[id+1]=v+R;
            Q.push({id+1,v+R});
        }
        if(vis[mp[a[id]]]==false){
            vis[mp[a[id]]]=true;
            int who=mp[a[id]];
            for(auto o:V[who]){
                if(value[o]>v+C){
                    value[o]=v+C;
                    Q.push({o,v+C});
                }
            }
        }
    }
    cout<<value[v]<<endl;
    return 0;
}

J.Houston, Are You There? (优雅暴力)

思路

看到这题n只有8所以脑子里应该要有点冲动的想法把。

我们考虑暴力出所有的状态。首先每个牌都可以翻转是把？所以我们现在有总共有

$2^8$种状态，这里可以考虑用二进制状压来遍历记录。

其次每个牌都可以对调位置是把？是不是有$A_{n}^{n}$ 种情况，这里我们用全排列来记录

所以总状态数为$2^8 ×8！$ 种情况 自己用电脑算算复杂度会不会超。然后我们还需要$O(n)$的时间来判断是否合法

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
const int oo=1e5+20;
 
int a[maxn],b[maxn];
 
int tmp[maxn],vis[maxn];
 
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
   // int tmp=1;
   // for(int i=1;i<=8;i++)tmp*=i;
  //  cout<<(tmp*(1<<8))<<endl;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++)if(i&(1<<j))swap(a[j],b[j]);
        vector<int>v;
        for(int j=0;j<n;j++)v.push_back(j);
        do{
            int flag=1;
            for(int j=1;j<n;j++){
                if(b[v[j-1]]!=a[v[j]]){
                    flag=0;break;
                }
            }
            if(flag){
                for(int j=0;j<n;j++){
                    tmp[j]=v[j]+1;
                    if((1<<(v[j]))&i)vis[j]=1;
                }
                for(int j=0;j<n;j++){
                    cout<<tmp[j]<<" "<<char(vis[j]?'b':'a')<<endl;
                }
                return 0;
            }
        }while(next_permutation(v.begin(),v.end()));
        for(int j=0;j<n;j++)if(i&(1<<j))swap(a[j],b[j]);
    }
    return 0;
}

K.Dahlia The Champion (gcd)

思路

首先会不会被盖住是不是说明他们的角度(叉积)不同,但是这个叉积是double类型的会有误差很难存是把， 所以我们可以考虑用$gcd$ 来缩小范围，比如点$(4,6)$ 和点$(2,3)$ 他们肯定会被盖住是把。那么点$(4,6)$ 其实可以变成点$(2,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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
const int oo=1e5+20;
 
 
int main()
{
    std::ios::sync_with_stdio(false);
    ll x0,y0,R,N;
    cin>>x0>>y0>>R>>N;
    set<pair<int,int> >st,st2,st3,st4;
    while(N--){
        ll x,y;
        cin>>x>>y;
        int tmp1=x,tmp2=y;
        x-=x0;y-=y0;
        if(sqrt(x*x+y*y)>R)continue;
        int gc=__gcd(abs(x),abs(y));x/=gc;y/=gc;
        st.insert({x,y});
    }
    cout<<st.size()<<endl;
    return 0;
}

Diposting di | Edited on

$sum[i][j]=从第i个到第j个和在一起浪费数$

$dp[i][j]=前i个分成j块的最小浪费​$

$dp[i][j]=dp[k][j-1]+sum[k+1][i]​$

假设x<y切y比x更优秀

那么

$dp[x][j-1]+sum[x+1][i]>=dp[y][j-1]+sum[y+1][i]$

调整一下

$dp[x][j-1]-dp[y][j-1]>=sum[y+1][i]-sum[x+1][i]\->dp[x][j-1]-dp[y][j-1]/sum[y+1][i]-sum[x+1][i]>=1​$

$dp[i][j]=dp[k][j-1]+(sum[i]-sum[k])-h[k+1]*(w[i]-w[k])​$

Diposting di

题意

给你两个由数字组成的字符串$S$,$T$ 长度为$1e3$，问你S中有多少个子序列的值大于字符串T；

思路

首先在比赛的时候一眼确定是$N^2$ 复杂度的DP，但是想了两三个小时却没想到怎么转移，各种构造$dp[i][j]$的含义。可是无功而返。

比赛结束后发现大家都用到了组合数。发现大家这题都用分两类来讨论做题。这时候才焕然大悟。

原来比T大的字符串可以分成两类根本不用瞎几把转移。

于是这题的解法很快就想到了，如果是大于的情况，那么只要第一个字符不是0，那么后面的几个字符串就随便取就行了。

大于的结束了接下来就是相等的情况。如果相等 那么肯定要考虑是从$S$串的哪个作为起点来构造子序列。并且这个S串的起点，的下一个点从哪里转移。这些都是可以DP的。于是我们基本的状态确定了，我们首先要确定目前构造到S串的哪个位置了。同时这个位置对于着T串的哪个位置，这样我们就可以开始转移。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e3+50;
typedef long long ll;
const ll mod=998244353;
ll dp[maxn][maxn];
ll C[maxn][maxn];
void add(ll &a,ll b){
    a+=b;
    if(a>=mod)a-=mod;
}
char s[maxn],t[maxn];
int main(){
    std::ios::sync_with_stdio(false);
    int T;
    C[0][0]=1;
    for(int i=1;i<=3000;i++){
        for(int j=0;j<=i;j++){
            if(j==0||j==i)C[i][j]=1;
            else add(C[i][j],C[i-1][j-1]+C[i-1][j]);
        }
    }
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        cin>>s+1>>t+1;
        for(int i=0;i<=n+10;i++){
            for(int j=0;j<=m+10;j++)dp[i][j]=0;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            if(s[i]=='0')continue;
            for(int j=m;j<=n;j++){
                add(ans,C[n-i][j]);
            }
        }
        ///dp[i][j]= 从后往前到当前S串第j的字符位置匹配到T串的第I个字符并且大于的个数
        for(int i=m;i;i--){
            for(int j=n;j;j--){
                dp[j][i]=dp[j+1][i];  ///因为包括了没有第j个字符的情况，所以如果第j+1个字符符合条件也可以
                if(t[i]==s[j])add(dp[j][i],dp[j+1][i+1]);
                /// 如果两个字符相同 那么答案就是少取这第J个字符同时还大于的数量
                if(t[i]<s[j])add(dp[j][i],C[n-j][m-i]);
                ///如果大于  那么答案就是后面的几个随便取几个就行了。
            }
        }
        cout<<(ans+dp[1][1])%mod<<endl;
    }
    return 0;
}

Diposting di

1001 AND Minimum Spanning Tree(位运算)

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
set<int>mp;
int get(int x){
    for(int i=0;i<30;i++){
        if((x&(1<<i))==0)return (1<<i);
    }
}
int main(){
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    int p=0;
    for(int i=1;i<=2e5;i*=2){
        p+=i;
        mp.insert(p);
    }
    while(t--){
        int n;
        cin>>n;
        int ans=0;
        vector<int>oo;
        for(int i=2;i<=n;i++){
            if(i%2==0)oo.push_back(1);
            else{
                if(mp.count(i)&&(i+1)<=n){
                    oo.push_back(i+1);
                }
                else if(mp.count(i)){
                    oo.push_back(1);
                    ans++;
                }
                else{
                    int u=get(i);
                    oo.push_back(u);
                }
            }
        }
        cout<<ans<<endl;
        for(int i=0;i<oo.size();i++){
            if(i)cout<<" ";
            cout<<oo[i];
        }
        cout<<endl;
    }
    return 0;
}

1007 Just an Old Puzzle （结论）

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;
typedef long long ll;
const int maxn=2e5+50;

int a[10][10];
int cal(int x,int y){
    int p=a[x][y];
    int cnt=0;
    for(int i=1;i<=x;i++){
        for(int j=1;j<=(i==x?y:4);j++){

            if(p<a[i][j])cnt++;
        }
    }
    return cnt;
}
int main(){
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int ix,iy;
        for(int i=1;i<=4;i++){
            for(int j=1;j<=4;j++){
                cin>>a[i][j];
                if(a[i][j]==0)ix=i,iy=j;
            }
        }
        int ans=ix;
        for(int i=1;i<=4;i++){
            for(int j=1;j<=4;j++){
                if(a[i][j]==0)continue;
                ans+=cal(i,j);
            }
        }
      //  cout<<"ans="<<ans<<endl;
        if(ans&1)cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }

    return 0;
}

1008 K-th Closest Distance （二分+主席树）

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int e5=1e6;
int rt[maxn*40],num[maxn*40],ls[maxn*40],rs[maxn*40];
int cnt;
void update(int &o,int pre,int l,int r,int val){
    o=++cnt;
    ls[o]=ls[pre],rs[o]=rs[pre];
    num[o]=num[pre]+1;
    if(l==r)return ;
    int mid=(l+r)/2;
    if(val<=mid)update(ls[o],ls[pre],l,mid,val);
    else update(rs[o],rs[pre],mid+1,r,val);
}
int query(int o,int l,int r,int val){///这个区间内小于等于这个数的个数
    if(l==r){
        return num[o];
    }
    int mid=(l+r)/2;
    if(val<=mid)return query(ls[o],l,mid,val);
    else return num[ls[o]]+query(rs[o],mid+1,r,val);
}
int n;
bool check(int mid,int K,int L,int R,int p){ ///K需要大于K个 值在P附近
    int l1=max(p-mid,1),r1=min(e5,p+mid);
    int numr1=query(rt[R],1,1e6,r1)-query(rt[L-1],1,1e6,r1);
    int numl1=query(rt[R],1,1e6,l1-1)-query(rt[L-1],1,1e6,l1-1);
    if(numr1-numl1>=K)return true;
    else return false;
}
int a[maxn];
int main(){
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int m;
        cin>>n>>m;
        cnt=0;
        for(int i=1;i<=n*40;i++){
            num[i]=0;ls[i]=0;rs[i]=0;rt[i]=0;
        }
        for(int i=1;i<=n;i++){
            cin>>a[i];
            update(rt[i],rt[i-1],1,1e6,a[i]);
        }
        int x=0;
        for(int i=1;i<=m;i++){
            int L,R,p,K;
            cin>>L>>R>>p>>K;
            L^=x;R^=x;p^=x;K^=x;
            if(L>R)swap(L,R);
            int l=0,r=1e6,ans;
            while(l<=r){
                int mid=(l+r)/2;
                if(check(mid,K,L,R,p)){
                    r=mid-1;
                    ans=mid;
                }
                else l=mid+1;
            }
            cout<<ans<<endl;
            x=ans;
        }
    }
    return 0;
}

1010Minimal Power of Prime（分类讨论）

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+50;
bool check[maxn];
ll prime[maxn],cnt;
void init(){
    for(int i=2;i<maxn;i++){
        if(!check[i]){
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            if(i*prime[j]>=maxn)break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
int get(ll &x){
    int ans=99999;
    for(ll i=1;i<=cnt&&1LL*prime[i]*prime[i]<=x;i++){
        if(x%prime[i]==0){
            int oo=0;
            while(x%prime[i]==0){
                oo++;
                x/=prime[i];
            }
            ans=min(oo,ans);
        }
    }
    return ans;
}
int main(){
    std::ios::sync_with_stdio(false);
    int t;
    init();
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        int ans=99999;
        if(n==1)ans=0;
        ll u=n;
        ans=get(u);
        if(u==1){
            cout<<ans<<endl;continue;
        }
        else{
            ll o4=powl(u,0.25)+0.5,o2=powl(u,0.5)+0.5,o3=powl(u,1.0/3.0)+0.5;
            if(o4*o4*o4*o4==u)ans=min(4,ans);
            else if(o3*o3*o3==u)ans=min(3,ans);
            else if(o2*o2==u)ans=min(2,ans);
            else ans=min(1,ans);
            cout<<ans<<endl;
        }
    }
    return 0;
}

Diposting di

1004.(二分加线段树DP)

因为二分的值越大 约束条件越少 所以满足二分的性质

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
#define bug cout<<"hehe"<<endl;
int n,k;
ll a[maxn];
ll dp[maxn<<2];
#define ls o<<1
#define rs o<<1|1
void push(int o){
    dp[o]=max(dp[ls],dp[rs]);
}
void build(int o,int l,int r){
    if(l==r){
        dp[o]=-1e18;return;
    }
    int mid=(l+r)/2;
    build(ls,l,mid);build(rs,mid+1,r);
    push(o);
}
ll query(int o,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r)return dp[o];
    int mid=(l+r)/2;
    ll res=-1e18;
    if(ql<=mid)res=max(res,query(ls,l,mid,ql,qr));
    if(qr>mid)res=max(res,query(rs,mid+1,r,ql,qr));
    return res;
}
void update(int o,int l,int r,int k,ll val){
    if(l==r){
        dp[o]=val;
        return ;
    }
    int mid=(l+r)/2;
    if(k<=mid)update(ls,l,mid,k,val);
    else update(rs,mid+1,r,k,val);
    push(o);
}
ll sum[maxn];
map<ll,int>mp;
map<ll,int>mpp;
vector<ll>ve;
bool check(ll mid){
    build(1,0,n+1);
    int first=lower_bound(ve.begin(),ve.end(),0)-ve.begin();
    update(1,0,n+1,first,0);
    for(int i=1;i<=n;i++){
        int id=mp[sum[i]];
        int ned=lower_bound(ve.begin(),ve.end(),sum[i]-mid)-ve.begin();
      //  cout<<"ned="<<ned<<" "<<sum[i]-mid<<endl;
        ll p=query(1,0,n+1,ned,n+1);
      //  cout<<"p="<<p<<endl;
      //  cout<<"id="<<id<<endl;
        update(1,0,n+1,id,p+1);
      //  cout<<"now query="<<query(1,0,n+1,id,id)<<endl;
        mp[sum[i]]++;
    }
  //  cout<<"query="<<query(1,0,n+1,1,n+1)<<endl;
    if(query(1,0,n+1,0,n+1)>=k){
        return true;
    }
    return false;
}



int main(){
    int t;
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        mp.clear();
        cin>>n>>k;
        ve.clear();
        for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i],ve.push_back(sum[i]);
        ve.push_back(0);
        sort(ve.begin(),ve.end());
        for(int i=0;i<ve.size();i++){
            if(mp.count(ve[i])==0)mp[ve[i]]=i;
        }
        ll l=-2e15,r=2e15,ans;
        mpp=mp;
        while(l<=r){
            ll mid=(l+r)/2;
            mp=mpp;
            if(check(mid)){
                r=mid-1;
                ans=mid;
            }
            else l=mid+1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

1006Fansblog (素数检测 + 威尔逊定理)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+50;
ll mod;
ll P;
ll Q;
int prime[maxn+1];
void getprime(){
    memset(prime,0,sizeof(prime));
    for(ll i=2;i<=maxn;i++){
        if(!prime[i])prime[++prime[0]]=i;
        for(ll j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
//****************************************************************
// Miller_Rabin 算法进行素数测试
//速度快，而且可以判断 <2^63的数
//****************************************************************
const int S=20;//随机算法判定次数，S越大，判错概率越小


//计算 (a*b)%c.   a,b都是long long的数，直接相乘可能溢出的
//  a,b,c <2^63
long long mult_mod(long long a,long long b,long long c)
{
    a%=c;
    b%=c;
    long long ret=0;
    while(b)
    {
        if(b&1){ret+=a;ret%=c;}
        a<<=1;
        if(a>=c)a%=c;
        b>>=1;
    }
    return ret;
}

void print(__int128 x)
{
    if(!x)
    {
        puts("0");
        return ;
    }
    string ret="";
    while(x)
    {
        ret+=x%10+'0';
        x/=10;
    }
    reverse(ret.begin(),ret.end());
    cout<<ret<<endl;
}

//计算  x^n %c
long long pow_mod(long long x,long long n,long long mod)//x^n%c
{
    if(n==1)return x%mod;
    x%=mod;
    long long tmp=x;
    long long ret=1;
    while(n)
    {
        if(n&1) ret=mult_mod(ret,tmp,mod);
        tmp=mult_mod(tmp,tmp,mod);
        n>>=1;
    }
    return ret;
}





//以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
//一定是合数返回true,不一定返回false
bool check(long long a,long long n,long long x,long long t)
{
    long long ret=pow_mod(a,x,n);
    long long last=ret;
    for(int i=1;i<=t;i++)
    {
        ret=mult_mod(ret,ret,n);
        if(ret==1&&last!=1&&last!=n-1) return true;//合数
        last=ret;
    }
    if(ret!=1) return true;
    return false;
}

// Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数，但概率极小)
//合数返回false;

bool Miller_Rabin(long long n)
{
    if(n<2)return false;
    if(n==2)return true;
    if((n&1)==0) return false;//偶数
    long long x=n-1;
    long long t=0;
    while((x&1)==0){x>>=1;t++;}
    for(int i=0;i<S;i++)
    {
        long long a=rand()%(n-1)+1;//rand()需要stdlib.h头文件
        if(check(a,n,x,t))
            return false;//合数
    }
    return true;
}
__int128 ksm(__int128 a,__int128 b){
    __int128 res=1;
    a%=mod;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    int t;
   // getprime();
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        ll o;
        cin>>o;
        P=o;
        mod=P;
        for(ll i=P-1;;i--){
            if(Miller_Rabin(i)){
                Q=i;
                break;
            }
        }
        __int128 ans=(-1+mod)%mod;
        for(ll i=P-1;i>Q;i--){
            ans=ans*ksm(i,mod-2)%mod;
        }
        ll u=ans;
        cout<<u<<endl;
    }
    return 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+50;
ll mod;
ll P;
ll Q;
int prime[maxn+1];
void getprime(){
    memset(prime,0,sizeof(prime));
    for(ll i=2;i<=maxn;i++){
        if(!prime[i])prime[++prime[0]]=i;
        for(ll j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
bool ok(ll x){
    for(int i=1;i<=prime[0];i++){
        if(x%prime[i]==0)return false;
    }
    return true;
}
__int128 ksm(__int128 a,__int128 b){
    __int128 res=1;
    a%=mod;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    int t;
    getprime();
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        ll o;
        cin>>o;
        P=o;
        mod=P;
        for(ll i=P-1;;i--){
            if(ok(i)){
                Q=i;
                break;
            }
        }
        __int128 ans=(-1+mod)%mod;
        for(ll i=P-1;i>Q;i--){
            ans=ans*ksm(i,mod-2)%mod;
        }
        ll u=ans;
        cout<<u<<endl;
    }
    return 0;
}

1007Find the answer (简单线段树操作)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;

ll a[maxn];
ll tot[maxn];
ll sum[maxn<<2];
ll num[maxn<<2];
#define ls o<<1
#define rs o<<1|1
void push(int o){
    sum[o]=sum[ls]+sum[rs];
    num[o]=num[ls]+num[rs];
}
void build(int o,int l,int r){
    if(l==r){
        sum[o]=0;
        num[o]=0;
        return;
    }
    int mid=(l+r)/2;
    build(ls,l,mid);build(rs,mid+1,r);
    push(o);
}
bool update(int o,int l,int r,int k,ll val){
    if(l==r){
        sum[o]=val;
        num[o]=1;
        return true;
    }
    int mid=(l+r)/2;
    if(k<=mid)update(ls,l,mid,k,val);
    else update(rs,mid+1,r,k,val);
    push(o);
}
int query(int o,int l,int r,ll val){
   // cout<<"o="<<o<<" l="<<l<<" r="<<r<<" val="<<val<<endl;
    if(l==r){
        return num[o];
    }
    int mid=(l+r)/2;
    int res=0;
    if(sum[rs]==val)return num[rs];
    if(sum[rs]<val){
        res+=num[rs];
        return res+query(ls,l,mid,val-sum[rs]);
    }
    else{
        return query(rs,mid+1,r,val);
    }
}
map<ll,int>mp;
ll b[maxn];
int main(){
    int t;
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        build(1,1,n);
        for(int i=1;i<=n;i++){
            cin>>a[i];
            tot[i]=tot[i-1]+a[i];
            b[i]=a[i];
        }
        sort(b+1,b+1+n);
        mp.clear();
        for(int i=1;i<=n;i++){
          //  cout<<b[i]<<" ";
            if(!mp.count(b[i]))mp[b[i]]=i;
        }
       // cout<<endl;
        for(int i=1;i<=n;i++){
            int id=mp[a[i]];
            if(tot[i]<=m)cout<<0<<" ";
            else{
               // cout<<"tot[i]-m"<<tot[i]-m<<endl;
                cout<<query(1,1,n,tot[i]-m)<<" ";
            }
            update(1,1,n,id,a[i]);
            mp[a[i]]++;
        }
        cout<<endl;
    }
    return 0;
}