2019年南昌邀请赛网络赛 解题日志

字数统计: 3.1k字   |   阅读时长: 18分

题目链接：https://www.jisuanke.com/contest/2290?view=challenges

A. PERFECT NUMBER PROBLEM(00:09 +1)

  • 暴力只能找出前4项，不妨直接oeis~
1
2
3
4
5
6
7
#include<bits/stdc++.h>
using namespace std;

int main(){
    puts("6\n28\n496\n8128\n33550336");
    return 0;
}

H. Coloring Game(00:16 +)

  • 推出公式便可
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>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
ll qpow(ll a,ll n){
    ll ret=1;
    while(n){
        if(n&1)ret=ret*a%mod;
        a=a*a%mod;
        n>>=1;
    }return ret;
}
int main(){
    int n;
    cin>>n;
    if(n==1)cout<<"1\n";
    else{
        cout<<4*qpow(3,n-2)%mod<<endl;
    }
    return 0;
}

M. Subsequence(00:39 +1)

  • 卡常！（加了个输入挂就过了）
  • 首先把某字符在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
#include <bits/stdc++.h>
using namespace std;
vector<int> id[256];
char s[100005];
int len;
void solve(){
    int pos=0;
    int lim=0;
    while(pos<len){
        int th=lower_bound(id[s[pos]].begin(),id[s[pos]].end(),lim)-id[s[pos]].begin();
        if(th==id[s[pos]].size()) break;
        lim=id[s[pos]][th]+1;
        pos++;
    }
    if(pos==len)puts("YES");
    else puts("NO");
}
int main(){
    read(s);
    len=strlen(s);
    for(int i=0;i<len;i++){
        id[s[i]].push_back(i);
    }
    int n;
    read(n);
    while(n--){
        read(s);
        len=strlen(s);
        solve();
    }
    return 0;
}

J. Distance on the tree(01:15 +2)

  • 通过题面很容易看出，首先边权转点权，然后以1为根建立树上主席树，那么(u,v)之间的贡献就是(u,1)的贡献加上(v,1)的贡献，减去2倍(1,lca)的贡献。
  • 区间第k大以及k的排名，都是很经典的主席树操作，注意离散化。
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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5+10;
int n,m,cntn,TOT;
int a[maxn],dt[maxn];
int T[maxn],lson[maxn<<6],rson[maxn<<6],c[maxn<<6];
void init_hash(){
    sort(dt+1,dt+1+cntn);
    cntn=unique(dt+1,dt+1+cntn)-dt-1;
}
int hs(int x){return lower_bound(dt+1,dt+1+cntn,x)-dt;}
int build(int l,int r){
    int rt=TOT++;
    c[rt]=0;
    if(l!=r){
        int mid=l+r>>1;
        lson[rt]=build(l,mid);rson[rt]=build(mid+1,r);
    }return rt;
}
int update(int rt,int pos,int val){
    int nrt=TOT++,tmp=nrt;
    c[nrt]=c[rt]+val;
    int l=1,r=cntn;
    while(l<r){
        int mid=l+r>>1;
        if(pos<=mid){
            lson[nrt]=TOT++,rson[nrt]=rson[rt];nrt=lson[nrt];rt=lson[rt];r=mid;
        }else{
            rson[nrt]=TOT++,lson[nrt]=lson[rt];nrt=rson[nrt];rt=rson[rt];l=mid+1;
        }c[nrt]=c[rt]+val;
    }return tmp;
}
int query(int lrt,int rrt,int lcart,int l,int r,int k){
    if(r<=k){
        int tmp=c[lrt]+c[rrt]-2*c[lcart];return tmp;
    }
    else{
        int mid=l+r>>1;
        int ret=0;
        if(1<=mid)ret+=query(lson[lrt],lson[rrt],lson[lcart],l,mid,k);
        if(k>mid) ret+=query(rson[lrt],rson[rrt],rson[lcart],mid+1,r,k);
        return ret;
    }
}
int rmq[maxn<<1];
struct ST{
    int mm[maxn<<1];
    int dp[maxn<<1][20];
    void init(int n){
        mm[0]=-1;
        for(int i=1;i<=n;i++){
            mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];dp[i][0]=i;
        }
        for(int j=1;j<=mm[n];j++){
            for(int i=1;i+(1<<j)-1<=n;i++){
                dp[i][j]=rmq[dp[i][j-1]]<rmq[dp[i+(1<<(j-1))][j-1]]?
                dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
            }
        }
    }
    int query(int a,int b){
        if(a>b)swap(a,b);
        int k=mm[b-a+1];
        return rmq[dp[a][k]]<=rmq[dp[b-(1<<k)+1][k]]?
        dp[a][k]:dp[b-(1<<k)+1][k];
    }
}st;
int F[maxn<<1],p[maxn];
int cnt;
struct edge{int to,nxt,v;};
edge e[maxn<<1];
int tot,head[maxn];

void adde(int u,int v,int w){
    e[tot].to=v;
    e[tot].v=w;
    e[tot].nxt=head[u];
    head[u]=tot++;
}

void dfs(int u,int pre,int dep){
    F[++cnt]=u;
    rmq[cnt]=dep;
    p[u]=cnt;
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        dfs(v,u,dep+1);
        F[++cnt]=u;
        rmq[cnt]=dep;
    }
}
void lca_init(int rt,int num){
    dfs(rt,rt,0);
    st.init(2*num-1);
}
int query_lca(int u,int v){return F[st.query(p[u],p[v])];}
void dfs_build(int u,int pre){
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        int pos = hs(e[i].v);
        T[v]=update(T[u],pos,1);
        dfs_build(v,u);
    }
}
int ls=0;
struct node{
    int u,v,k;
}q[maxn];
int main(){
    memset(head,-1,sizeof head);
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        dt[++cntn]=w;
        adde(u,v,w);adde(v,u,w);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].k);
        dt[++cntn]=q[i].k;
    }
    init_hash();
    lca_init(1,n);
    T[1]=build(1,cntn);
    dfs_build(1,0);
    for(int i=1;i<=m;i++){
        printf("%d\n",query(T[q[i].u],T[q[i].v],T[query_lca(q[i].u,q[i].v)],1,cntn,hs(q[i].k)));
    }
    return 0;
}

I. Max answer(02:58 +)

  • 对于选中的区间，如果最小值为正数，明显答案用单调栈预处理然后直接计算
  • 如果最小值为负数，一定选中完整连续的负数区间，有可能会覆盖到别的连续负数区间，前缀和讨论便可。
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
#include<bits/stdc++.h>
using namespace std;
int n,a[505050],cntz=-1,cntf=-1,cnt=0;
vector<int> ztv[500050],ftv[500050];
int l[500005],r[500005];
long long sm[500050],md[500050];
long long pre[500005];
long long ans=0;
long long presum[500005],sufsum[500005],presummax[500005],sufsummax[500005],prepre[500005];
long long getmin(int x){
    long long sum=0;
    for(int i=0;i<ftv[x].size();i++) sum=min(sum,1LL*ftv[x][i]);
    return sum;
}
long long getsum(int fg,int x){
    long long sum=0;
    if(fg){
        for(int i=0;i<ztv[x].size();i++) sum=sum+ztv[x][i];
    }
    else for(int i=0;i<ftv[x].size();i++) sum=sum+ftv[x][i];
    return sum;
}
long long getpresum(int x,int y){
    if(x==0) return presum[y];
    else return presum[y]-presum[x-1];
}
long long getpre(int x,int y){
    if(x==0) return pre[y];
    else return pre[y]-pre[x-1];
}
void dd(vector<int> &vec){
    deque<pair<int,int> >q;
    q.push_back(make_pair(-1,-1));
    for(int i=0;i<vec.size();i++){
        while(q.back().first>=vec[i])q.pop_back();
        l[i]=q.back().second;
        q.push_back(make_pair(vec[i],i));
    }
    while(q.size()>1)q.pop_back();
    for(int i=vec.size()-1;i>=0;i--){
        while(q.back().first>=vec[i])q.pop_back();
        r[i]=q.back().second;
        q.push_back(make_pair(vec[i],i));
    }
    pre[0]=vec[0];
    for(int i=1;i<vec.size();i++) pre[i]=pre[i-1]+vec[i];
    for(int i=0;i<vec.size();i++){
        int ll,rr;
        if(l[i]==-1) ll=0;
        else ll=l[i]+1;
        if(r[i]==-1) rr=vec.size()-1;
        else rr=r[i]-1;
        ans=max(ans,vec[i]*getpre(ll,rr));
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int flag=0;
    for(int i=1;i<=n;i++){
        if(a[i]>0){
            if(flag>0){
                ztv[cntz].push_back(a[i]);flag=1;
            }
            else{
                if(cntz!=-1){
                    sm[cnt]=getsum(1,cntz);
                    md[cnt]=1;
                    //cout<<cnt<<" "<<sm[cnt]<<" "<<md[cnt]<<" "<<ztv[cntz].size()<<endl;
                    cnt++;
                }

                cntz++;
                ztv[cntz].push_back(a[i]);
                flag=1;
            }
        }
        else{
            if(flag<0){
                ftv[cntf].push_back(a[i]);
            }
            else{
                if(cntf!=-1){
                    sm[cnt]=getsum(0,cntf);
                    md[cnt]=getmin(cntf);
                    //cout<<cnt<<" "<<sm[cnt]<<" "<<md[cnt]<<" "<<ftv[cntf].size()<<endl;
                    cnt++;
                }

                cntf++;
                ftv[cntf].push_back(a[i]);
            }
            flag=-1;
        }
    }
    if(flag==1){
        sm[cnt]=getsum(0,cntf);
        md[cnt]=getmin(cntf);
        cnt++;
        if(cntz!=-1){
            sm[cnt]=getsum(1,cntz);
            md[cnt]=1;
            cnt++;
        }
    }
    else{
        sm[cnt]=getsum(1,cntz);
        md[cnt]=1;
        cnt++;
        if(cntf!=-1){
            sm[cnt]=getsum(0,cntz);
            md[cnt]=getmin(cntf);
            cnt++;
        }
    }
    for(int i=0;i<=cntz;i++) dd(ztv[i]);
    presum[0]=sm[0];
    for(int i=1;i<cnt;i++) presum[i]=sm[i]+presum[i-1];
    sufsum[cnt-1]=sm[cnt-1];
    for(int i=cnt-2;i>=0;i--) sufsum[i]=sm[i]+sufsum[i+1];
    presummax[0]=presum[0];
    for(int i=1;i<cnt;i++) presummax[i]=max(presummax[i-1],presum[i]);
    sufsummax[cnt-1]=sufsum[cnt-1];
    for(int i=cnt-2;i>=0;i--) sufsummax[i]=max(sufsummax[i+1],sufsum[i]);

    for(int i=0;i<cnt;i++){
        if(sm[i]>0) continue;
        else {
            long long lft,rgt;
            if(i==0) lft=0;
            else lft=min(0LL,getpresum(0,i-1)-presummax[i-1]);
            if(i==cnt-1) rgt=0;
            else rgt=min(0LL,getpresum(i+1,cnt-1)-sufsummax[i+1]);
            ans=max(ans,md[i]*(lft+rgt+sm[i]));
        }
    }
    printf("%lld\n",ans);
    return 0;
}
/*
12
1 -2 1 0 -2 -3 5 1 0 1 -3 8
6
-2 -6 3 -2 -4 -3
*/

K. MORE XOR(03:34 +)

  • 找规律发现，当r-l+1为偶数时，g(l,r)=0；
  • 进一步发现答案贡献间隔为4，预处理出4个前缀和数组，然后对于每个查询O(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
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>
using namespace std;
int n,m,T,a[200000];
int pre1[200000],pre2[200000],pre3[200000],pre4[200000];
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        pre1[1]=a[1];
        pre1[2]=pre1[1];
        pre1[3]=pre1[2];
        pre1[4]=pre1[3];
        pre2[2]=a[2];
        pre2[3]=pre2[2];
        pre2[4]=pre2[3];
        pre3[3]=a[3];
        pre3[4]=pre3[3];
        pre4[4]=a[4];
        for(int i=5;i<=n;i++){
            if(i%4==1) pre1[i]=pre1[i-1]^a[i];
            else pre1[i]=pre1[i-1];
            if(i%4==2) pre2[i ]=pre2[i-1]^a[i];
            else pre2[i]=pre2[i-1];
            if(i%4==3) pre3[i]=pre3[i-1]^a[i];
            else pre3[i]=pre3[i-1];
            if(i%4==0) pre4[i]=pre4[i-1]^a[i];
            else pre4[i]=pre4[i-1];
        }
        cin>>m;
        while(m--){
            int l,r;
            scanf("%d %d",&l,&r);
            int maxg,maxo,ming,mino;
            if(l%2==0){
                mino=l;
                ming=l+1;
            }
            else{
                mino=l+1;
                ming=l;
            }
            if(r%2==0){
                maxo=r;
                maxg=r-1;
            }
            else{
                maxo=r-1;
                maxg=r;
            }
            int ans=0;
            //cout<<ming<<" "<<maxg<<" "<<mino<<" "<<maxo<<endl;
            if((maxg-ming)%4==0){
                if(ming%4==1){
                    ans^=(pre1[maxg]^pre1[ming-1]);
                }
                else{
                    ans^=(pre3[maxg]^pre3[ming-1]);
                }
            }
            if((maxo-mino)%4==0){
                if(mino%4==2){
                    ans^=(pre2[maxo]^pre2[mino-1]);
                }
                else{
                    ans^=(pre4[maxo]^pre4[mino-1]);
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

C. Angry FFF Party(04:22 +2)

  • 打表发现预处理29位已经足够覆盖输入的所有情况了；
  • 直接贪心求最小字典序的选择方式。
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
import java.util.Scanner;
import java.math.BigInteger;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		//BigInteger[] fib = new BigInteger[50];
		BigInteger[] arry = new BigInteger[50];
		//fib[1] = fib[2] = BigInteger.ONE;
		arry[1] = arry[2] = BigInteger.ONE;
		for (int i = 3; i < 30; ++ i) {
			//fib[i] = fib[i - 1].add(fib[i - 2]);
			arry[i] = cal(cal(BigInteger.valueOf(i)));
            
            //if(i < 10) System.out.println(arry[i]);
		}
		while (T --> 0) {
			BigInteger W = in.nextBigInteger();
			int[] ans = new int[35];
			int cnt = 0;
			for (int i = 29; i >= 6; -- i) {
				if (W.compareTo(arry[i]) >= 0) {
					W = W.subtract(arry[i]);
					ans[cnt] = i; cnt ++;
				}
			}
			if (W.compareTo(BigInteger.valueOf(10)) == 1) {
				System.out.println(-1);
			}
			else {
				if (W.equals(BigInteger.valueOf(1)) == true) {
                    System.out.print("1");
                }
                else if (W.equals(BigInteger.valueOf(2)) == true) {
                    System.out.print("1 2");
                }
                else if (W.equals(BigInteger.valueOf(3)) == true) {
                    System.out.print("1 2 3");
                }
                else if (W.equals(BigInteger.valueOf(4)) == true) {
                    System.out.print("1 2 4");
                }
                else if (W.equals(BigInteger.valueOf(5)) == true) {
                    System.out.print("1 2 3 4");
                }
                else if (W.equals(BigInteger.valueOf(6)) == true) {
                    System.out.print("1 5");
                }
                else if (W.equals(BigInteger.valueOf(7)) == true) {
                    System.out.print("1 2 5");
                }
                else if (W.equals(BigInteger.valueOf(8)) == true) {
                    System.out.print("1 2 3 5");
                }
                else if (W.equals(BigInteger.valueOf(9)) == true) {
                    System.out.print("1 2 4 5");
                }
                else if (W.equals(BigInteger.valueOf(10)) == true) {
                    System.out.print("1 2 3 4 5");
                }
                if (W.equals(BigInteger.ZERO) == false && cnt != 0)
                    System.out.print(" ");
				for (int i = cnt - 1; i >= 0 ; -- i) {
					System.out.print(ans[i]);
					if (i != 0) System.out.print(" ");
				}
				System.out.println();
			}
		}
	}
	static BigInteger[][] c = new BigInteger[2][2];
	public static BigInteger cal(BigInteger n) {
		BigInteger[][] d = new BigInteger[2][2];
		BigInteger[][] a = new BigInteger[2][2];
		d[0][0] = BigInteger.ONE;
		d[0][1] = BigInteger.ZERO;
		d[1][0] = BigInteger.ZERO;
		d[1][1] = BigInteger.ONE;
		a[0][0] = BigInteger.ONE;
		a[0][1] = BigInteger.ONE;
		a[1][0] = BigInteger.ONE;
		a[1][1] = BigInteger.ZERO;
		while (n.equals(BigInteger.ZERO) == false) {
			if (n.mod(BigInteger.valueOf(2)).equals(BigInteger.ONE) == true) {
				mmul(d, a);
				for (int i = 0; i < 2; ++ i) {
					for (int j = 0; j < 2; ++ j) {
						d[i][j] = c[i][j];
					}
				}
			}
			mmul(a, a);
			for (int i = 0; i < 2; ++ i) {
				for (int j = 0; j < 2; ++ j) {
					a[i][j] = c[i][j];
				}
			}
			n = n.divide(BigInteger.valueOf(2));
		}
		return d[1][0];
	}
	public static void mmul(BigInteger[][] a, BigInteger[][] b) {
		for (int i = 0; i < 2; ++ i) {
			for (int j = 0; j < 2; ++ j) {
				c[i][j] = BigInteger.ZERO;
				for (int k = 0; k < 2; ++ k) {
					c[i][j] = c[i][j].add(a[i][k].multiply(b[k][j]));
				}
			}
		}
	}
}
赏

谢谢打赏

支付宝
微信

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

iOS Developer, ACMer, ...