你最愿意做的哪件事，才是你的天赋所在

0%

Gym-102091

发表于 Valine：

题目链接

Gym-102091

A

思路

队友写的，我不会，听说是分治+一堆乱七八糟的数据结构

代码实现
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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#pragma GCC optimize(2)
#define up(i,a,b)  for(int i=a;i<b;i++)
#define dw(i,a,b)  for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
	char ch = getchar(); ll x = 0, f = 1;
	while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 1e5 + 10;
int cnt[N];
int ans[N];
int n, m;
int hi[N];
struct tr {
	int maxx, pos;
	tr operator+(const tr temp)const {
		tr now = *this;
		tr res;
		if (now.maxx >= temp.maxx)
		{
			res.maxx = now.maxx;
			res.pos = now.pos;
		}
		else {
			res.maxx = temp.maxx;
			res.pos = temp.pos;
		}
		return res;
	}
}tree[N<<2];
void update(int l, int r, int root,int pos,int val)
{
	if (l == r) {
		tree[root].maxx = val;
		tree[root].pos = pos;
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid)update(lson, pos, val);
	else update(rson, pos, val);
	tree[root] = tree[lrt] + tree[rrt];
}
tr query(int l, int r, int root, int L, int R)
{
	if (L > R)return tr{ 0,0 };
	if (L <= l && r <= R)
	{
		return tree[root];
	}
	int mid = (l + r) >> 1;
	tr ans;
	tr anss;
	bool flag = 1;
	if (L <= mid)
	{
		flag = 0;
		ans = query(lson, L, R);
	}
	if (R > mid)
	{
		if (flag)ans = query(rson, L, R);
		else {
			anss = query(rson, L, R);
			if (ans.maxx < anss.maxx)ans = anss;
		}
	}
	return ans;
}
int solve(int l,int r,int d)
{
	if (l > r)return -1;
	tr now = query(1, n, 1, l, r);
	cnt[now.pos] = d;
	ans[now.pos] = solve(l, now.pos - 1, d + 1) + 1;
	int anss = ans[now.pos], dd= 0;
	int pp = now.pos;
	while (pp < r)
	{
		tr temp = query(1, n, 1, pp + 1, r);
		if (temp.maxx == hi[pp])
		{
			dd = solve(pp + 1, temp.pos - 1, d + 1);
			anss = max(dd + 1, anss);
			ans[temp.pos] = dd + 1;
			ans[pp] = max(ans[pp], dd + 1);
			cnt[temp.pos] = d;
			pp = temp.pos;
		}
		else break;
	}
	ans[pp] = max(ans[pp], solve(pp + 1, r, d + 1) + 1);
	anss = max(ans[pp], anss);
	return anss;
}
int main()
{
	n = read(), m = read();
	upd(i, 1, n)hi[i] = read(),update(1,n,1,i,hi[i]);
	solve(1, n, 1);
	int x, y;
	while (m--)
	{
		x = read(), y = read();
		if (y == 0)
		{
			printf("%d\n", ans[x]);
		}
		else {
			if (hi[x] > hi[y])swap(x, y);
			if (y > x)
			{
				tr temp = query(1, n, 1, x, y - 1);
				if (temp.maxx >= hi[y])printf("%d\n", 0);
				else printf("%d\n", -cnt[y] + cnt[x]);
			}
			else {
				tr temp = query(1, n, 1, y + 1, x);
				if (temp.maxx >= hi[y])printf("%d\n", 0);
					else printf("%d\n", -cnt[y] + cnt[x]);
				}
		}
	}
	return 0;
}

D

思路
代码实现

签到题，特判最后一位数即可

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
//
// Created by 91917 on 2020/5/8.
//

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        scanf("%d",&n);
        if (n == 0 || n == 1) {
            printf("%d\n",n);
            continue;
        }
        int pre, nex;
        scanf("%d",&pre);
        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            scanf("%d",&nex);
            if (i == n - 2) {
                if (nex - pre > 20)ans += 2;
                else ans++;
            } else if (nex - pre > 20) {
                ans++;
                pre = nex;
            }
        }
        printf("%d\n",ans);
    }
}

F

思路

从杨辉三角中找不能被7整除的，打个表发现规律是28，28*28，跟7的次幂有关。按照打表找出的规律进行匹配就可以了。

代码实现
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<vll>
#define pii pair<int,int>
#define pll pair<ll>
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll pre[200];
ll num[100];
int main(){
  pre[0]=1;
  ll inv2 = inv(2);
  for(int i=1;i<=100;i++){pre[i]=1ll*pre[i-1]*28%mod;}
  int t;
  scanf("%d",&t);
  for(int cas=1;cas<=t;cas++){
      ll x;
      scanf("%lld",&x);
      unsigned  ll xx=x;
      int cnt = 0;
      while(x){
          num[++cnt]=x%7;
          x/=7;
      }
      ll ans=0,lst=1;
      for(int i=cnt;i;i--){
          ans=(ans+lst*pre[i-1]%mod*((1ll*num[i]*(num[i]+1))/2)%mod)%mod;
          lst=(lst * (num[i]+1))%mod;
      }
      ans=(ans+lst)%mod;
      if((xx+1)%2==0)ans=((((xx+1)/2)%mod*((xx+2)%mod))%mod-ans+mod)%mod;
      else ans=((((xx+2)/2)%mod*((xx+1)%mod))%mod-ans+mod)%mod;
      printf("Case %d: %lld\n",cas,ans);
  }
}
打表代码
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<vll>
#define pii pair<int,int>
#define pll pair<ll>
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const int N = 1e5+10;
int fac[N];
int in[N];
int lacus(int n,int m){
    while(n&&m){
        if(m%7>n%7)return 0;
        m/=7;
        n/=7;
    }
    return 1;
}
int main(){
  fac[0]=1;
  for(int i=1;i<N;i++)fac[i]=1ll*fac[i-1]*i%mod;
  in[N-1]=inv(fac[N-1]);
  for(int i=N-2;i>=0;i--)in[i]=1ll*in[i+1]*(i+1)%mod;
  ll sum = 0;
  for(int i=0;i<=500;i++){
      int cnt = 0;
      for(int j=0;j<=i;j++){
          if(lacus(i,j))cnt++;
      }
      sum+=cnt;
      printf("%d:%d %lld\n",i,cnt,sum);
  }
}

G

思路

裸的强连通分量题目，套上板子即可

代码实现
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>
using namespace std;
const int N = 1e5+10;
struct node{
    int v,next;
}edge[N];
int dfn[N],low[N],st[N];
int head[N],vis[N],cnt,tot,ans,index_;
void add(int u,int v){
    edge[cnt].next=head[u];
    edge[cnt].v=v;
    head[u]=cnt++;
}
void tarjan(int x){
    dfn[x]=low[x]=++tot;
    st[++index_]=x;
    vis[x]=1;
    for(int i=head[x];i!=-1;i=edge[i].next){
        if(!dfn[edge[i].v])//如果没有被vis
        {
            tarjan(edge[i].v);
            low[x]=min(low[x],low[edge[i].v]);
        }else if(vis[edge[i].v]){
            low[x]=min(low[x],dfn[edge[i].v]);
        }
    }
    if(low[x]==dfn[x]){
        int cnt = 0;
        do{
            vis[st[index_]]=0;
            index_--;
            cnt++;
        }while(x!=st[index_+1]);
        ans++;
    }
    return ;
}
int main(){
    int n,m;
    int t;
    scanf("%d",&t);
    while(t--) {
        ans=0;
        cnt=0;
        memset(head, -1, sizeof(head));
        memset(vis,false,sizeof(vis));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(st,0,sizeof(st));
        scanf("%d %d", &n, &m);
        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            add(u, v);
        }
        for (int i = 0; i < n; i++) {
            if (!dfn[i])tarjan(i);
        }
        printf("%d\n", ans);
    }
}

H

思路

一开始读错了题目，后面队友纠正了后发现是中国剩余定理，因为题目保证了x小于N1,N2,N3的最小值，所以x^3就在n1n2n3的范围中，因此直接中国剩余定理，然后二分开方就可以了。

代码实现
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fin(a,n) for(int i=a;i<=n;i++)
const int maxn=20;
ll a1[20],b1[20];
long long sqrt3(long long n) {
    long long l=1,r=(long long)pow(n*1.0, 1.0 / 3) + 1,mid;
    while(l<=r) {
        mid=(l+r)>>1;
        if(mid*mid*mid==n) return mid;
        else if(mid*mid*mid>n) r=mid-1;
        else l=mid+1;
    }
    return -1;
}
ll mul(ll a,ll b,ll mod)//求（a*b）%mod ，防止a*b炸ll 
{
    ll ans=0;
    while(b>0)
    {
        if(b&1)ans=(ans+a)%mod;//如果b对答案有贡献
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得 
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    ll ans=exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-(a/b)*y;
    return ans;
}
ll china(int n)//中国剩余定理 
{
    ll M=1,ans=0,x,y;
    fin(1,n)M*=b1[i];
    fin(1,n)
    {
        ll a,b;
        a=M/b1[i];//此处的按照ax+by=1的形式，因为互素所以等号右边恒为1.
        b=b1[i];
        exgcd(a,b,x,y);
        x=(x%b+b)%b;//求出最小的x
        ans=(ans+mul(mul(a,x,M),a1[i],M))%M;//此处对应求和即ai*xi*mi
    }
    return (ans+M)%M;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--) {
        int n;
        n=3;
        fin(1, n)scanf("%lld", &b1[i]);
        fin(1, n)scanf("%lld", &a1[i]);
        fin(1, n)a1[i] = (a1[i] % b1[i] + b1[i]) % b1[i];//预处理数据
        ll tans = china(n);
        printf("%lld\n", sqrt3(tans));
    }
}

J

思路

赛时没想出来，题解是求导，根据求导公式，把△x用1e-15代替，误差很小。

代码实现
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
//
// Created by 91917 on 2020/5/8.
//
#include<bits/stdc++.h>
using namespace std;
#define  ll long long
int main(){
    ll l,r;
        while(~scanf("%lld  %lld", &l, &r)&&(l||r)) {
            double ans = 0;
            for (ll i = l; i <= r; i++) {
                ans += pow(i, -1.0 * 2.0 / 3.0);
            }
            ans /= 3;
            int w = 15;
            if (ans - 10 > 1e-9) {
                ans /= 10;
                printf("%.5lfE-014\n", ans);
            } else {
                while (ans < 1e-9 + 1) {
                    ans *= 10;
                    w++;
                }
                printf("%.5lfE-0%d\n", ans, w);
            }
        }
}

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#include <iomanip>
#pragma GCC optimize(2)
#define up(i,a,b)  for(int i=a;i<b;i++)
#define dw(i,a,b)  for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
	char ch = getchar(); ll x = 0, f = 1;
	while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 1e6 + 10;
const int nn = 1e6 + 1;
struct nd {
	int st, val, ed;
	bool operator<(const nd &temp)const {
		return ed > temp.ed;
	}
};
priority_queue<nd>q;
int val[N << 2];
void pushup(int root)
{
	val[root] = val[lrt] + val[rrt];
}
void build(int l, int r, int root)
{
	val[root] = 0;
	if (l == r)return;
	int mid = (l + r) >> 1;
	build(lson);
	build(rson);
}
void update(int l, int r, int root, int pos, int v)
{
	if (l == r)
	{
		val[root] += v;
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid)update(lson, pos, v);
	else update(rson, pos, v);
	pushup(root);
}
int query(int l, int r, int root, int k)
{
	if (k > val[root])return -1;
	if (l == r)
	{
		return l;
	}
	int mid = (l + r) >> 1;
	if (val[lrt] < k) {
		k -= val[lrt];
		return query(rson, k);
	}
	else return query(lson, k);
}
int n, opt, x, t;
int cs = 0;
int main()
{
	t = read();
	while (t--)
	{
		n = read();
		int x, y, z;
		build(1, nn, 1);
		while (!q.empty())q.pop();
		printf("Case %d:\n", ++cs);
		upd(i, 1, n)
		{
			opt = read();
			if (opt == 1)
			{
				x = read(), y = read(), z = read();
				q.push(nd{ x,y,z });
				update(1, nn, 1, y, 1);
			}
			else {
				x = read(), y = read();
				nd temp;
				while (q.size())
				{
					temp = q.top();
					if (temp.ed < x)
						q.pop(), update(1, nn, 1, temp.val, -1);
					else break;
				}
				int ans = query(1, nn, 1, y);
				printf("%d\n", ans);
			}
		}
	}
	return 0;
}

L

思路

就是二分然后n^2匹配，注意使用快读，不用快读必然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
52
53
54
55
56
57
58
//
// Created by 91917 on 2020/5/8.
//
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e3+10;
int n,m;
int grp[N][N];
int getsum(int x1,int y1,int x2,int y2){
    return grp[x2][y2]-grp[x2][y1-1]-grp[x1-1][y2]+grp[x1-1][y1-1];
}
inline void read(int &a){
    char ch= getchar(),w=1;a=0;
    while (ch<'0' || ch>'9') {if (ch=='-') w=-1;ch=getchar();}
    while (ch>='0' && ch<='9') a=a*10+ch-'0', ch=getchar();
    a=a*w;
}
bool check(int mid){
    for(int i=1;i<=n-mid+1;i++){
        for(int j=1;j<=m-mid+1;j++){
            int num = getsum(i,j,i+mid-1,j+mid-1);
            if(num==1||num==0) {
                return true; }
        }
    }
    return false;
}
void solve(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&grp[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            grp[i][j]+=grp[i][j-1];
            grp[i][j]+=grp[i-1][j];
            grp[i][j]-=grp[i-1][j-1];
        }
    }
    int l=0,r=n*m+1;
    int ans;
    while(l<=r){
        int mid = (l+r)>>1;
        if(check(mid)){
            l=mid+1;
            ans=mid;
        }else r=mid-1;
    }
    printf("%d\n",ans);
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--)solve();
}
-------------你最愿意做的哪件事才是你的天赋所在-------------