img

2023年广东工业大学新生赛

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std; 
int t,x,y,z,sum,ans;
int main() {
    cin>>t;
    while(t--)
    {
        cin>>x>>y>>z;
        sum=(y+z)%7;
        ans=sum+x;
        if(ans%7==0)
        ans=7;
        else
        ans=(sum+x)%7;
        cout<<ans<<endl;
    }
    return 0;
}

B

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; 
int n,m,k,sum,ans,a[100005],b[100005];
string s;
int main() {
	cin>>n>>m;
	while(m--)
	{
		cin>>k>>s;
		if(s=="AC"&&a[k]==0)
		{
			sum++;
			a[k]=1;
			ans+=b[k];
		}
		else
		b[k]++;
		
	}
    cout<<sum<<" "<<ans<<endl;
	return 0;
}

C

或5或9即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

void solve(){
    ll n ;
    cin>>n;
    if(n==2ll)
        cout<<5<<endl;
    else
        cout<<9<<endl;
}

int main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t = 1;
    cin>>t;
    while(t--){
        solve();
    }
}

D

思路没问题

左边的数字一定比右边的数字的5要少一些，最好也是等于

右边的数字一定要比左边的数字6要少一些，最好也是等于

因此可以先枚举6

如果右边比较多就是0了

接下来给左边乘上一样的6

然后×5，相等就输出答案

不然就是-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
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

void solve(){
    ll x,y;
    cin>>x>>y;
    ll ans =0 ;
    ll cnt1=0,cnt2=0;
    ll xx = x,yy=y;
    while(xx%6==0) xx/=6,cnt1++;
    while(yy%6==0) yy/=6,cnt2++;
    
    if(cnt1<cnt2) {
        cout<<-1<<endl;return;
    }
    for(ll i=0;i<cnt1-cnt2;i++){
        x/=6;ans++;
    }
    while(x<y){
        x*=5;ans++;
    }
    if(x==y)
        cout<<ans<<endl;
    else
        cout<<-1<<endl;
}

signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    ll t = 1;
    cin>>t;
    while(t--){
        solve();
    }
}

E

使得一个连续的段使得0和1的个数最多并且相等

想个思路，前缀和，不过我们完全可以把0看成-1吗，兄弟。这样不就变成了找区间和为0了

也就是两个部分前缀和为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
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

void solve(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int &x:a)cin>>x;
    vector<int> pre(n,a[0]?1:-1);
    for(int i=1;i<n;i++)
        pre[i] = pre[i-1]+(a[i]?1:-1);
    map<int,int> mp;
    mp[0] = -1;
    for(int i=0;i<n;i++){
        if(mp.find(pre[i])!=mp.end())
            continue;
        mp[pre[i]] = i;
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        int x = pre[i];
        ans =max(ans,i-mp[x]);
    }
    cout<<ans<<endl;
}

int main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t = 1;
    while(t--){
        solve();
    }
}

或者：

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
#include <bits/stdc++.h>
 
using namespace std;
const int N = 1e5 + 10;
 
int n;
map<int, int> a;
vector<int> v[N];
int main()
{
    cin >> n;
    int sum = 0;
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if (x == 0)
            sum--;
        else
            sum++;
        if(!sum)
        res=max(res,i);
        if (!a[sum])
            a[sum] = i;
        //最早出现
        else
            res = max(res, i - a[sum]);
    }
    cout << res << endl;
 
    return 0;
}

F

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define int long lon
const int N = 2e5+10; 
void solve()
{
    int n,V;
    map<int,int>mp;
    cin>>n>>V;
    vector<int>t(n);
    for(int i=0;i<n;i++){
        cin>>t[i];
    }
    sort(t.begin(),t.end());
    int mx=0;
    for(int i=n-1;i>=0;){
        int j=i;
        while(t[j]==t[i]&&j>=0)j--;
        mp[t[i]%V]=mp[(t[i]+1)%V]+i-j;
        mx=max(mx,mp[t[i]%V]);
        i=j;
    }
    cout<<n-mx<<endl;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T(1);
    cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

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
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
//kira doki
int n,sumk,sumd,prek[100010],sufd[100010];
char s[100010];
signed main(){
    std::ios::sync_with_stdio(false);
    cin>>n>>s+1;
    for(int i=1;i<=n;i++){
    	prek[i]=prek[i-1];
    	if(s[i]=='k'&&sumk==0)sumk++;
    	else if(s[i]=='i'&&sumk==1)sumk++;
    	else if(s[i]=='r'&&sumk==2)sumk++;
    	else if(s[i]=='a'&&sumk==3)sumk++;
    	if(sumk==4)prek[i]+=4,sumk=0;
	}
    for(int i=n;i>=1;i--){
    	sufd[i]=sufd[i+1];
    	if(s[i]=='i'&&sumd==0)sumd++;
    	else if(s[i]=='k'&&sumd==1)sumd++;
    	else if(s[i]=='o'&&sumd==2)sumd++;
    	else if(s[i]=='d'&&sumd==3)sumd++;
    	if(sumd==4)sufd[i]+=4,sumd=0;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(prek[i]&&sufd[i+1])ans=max(prek[i]+sufd[i+1],ans);
	cout<<ans<<endl;
	return 0;
}

H

根据辗转相除法即可以得到与ai无关

然后暴力枚举b和c数组

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;

#define ll long long
#define endl "\n"

inline ll gcd(ll x, ll y) {
    return y == 0 ? x : gcd(y, x % y);
}

void solve(){
    ll n;
    cin>>n;
    vector<ll> a(n),b(n),c(n);
    for(ll &x:a) cin>>x;
    for(ll &x:b) cin>>x;
    for(ll &x:c) cin>>x;
    ll g = 0;
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    for(ll i=0;i<n-1;i++){
        g= gcd(g,a[i]-a[i+1]);
    }
    ll an_1 = a[n-1];
    ll mx = 0,mi = 2e18;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            ll ng = gcd(g,an_1+b[i]+c[j]);
            mx =max(mx,ng);
            mi = min(mi,ng);
        }
    }   
    cout<<mi<<" "<<mx<<endl;
}

signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    ll t = 1;
    while(t--){
        solve();
    }
}

I

当我们使用第i个骰子时， Ⅰ.从前方直接到达该格子，若当前位置为j，则前方位置应为j-ai,故dpj=min(dpj,dp[j-ai]+1); Ⅱ.反弹到达该格子，若当前位置为j，则起始位置y满足方程式(n-y)+(n-j)=ai,即y=2*n-ai-j,故

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
#include<bits/stdc++.h>
#define int long long
const int INF=1e10;
using namespace std;
int n,m;
int a[1010];
map<int,int>dp;
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=-1000;i<=1000;i++)dp[i]=INF;
    dp[0]=0;
    for(int i=1;i<=m;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        for(int j=n;j>=-1000;j--)
        {//注意倒着存值！！！因为转移只能一次性转移
            int x=j-a[i];
            dp[j]=min(dp[j],dp[x]+1);
            //可以由不用反弹来
            int y=2*n-a[i]-j;
            //反弹了
            if(y<=n)dp[j]=min(dp[j],dp[y]+1);  
            
        }
    }
    if(dp[n]!=INF)cout<<dp[n]<<endl;
    else cout<<"-1"<<endl;;
}

J

贪心加优先队列

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
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"

ll n,m,x,y;
ll grid[1005][1005] ={0};
ll vis[1005][1005] ={0};
bool ifon(ll x,ll y){
    return x>=0&&x<n&&y>=0&&y<m;
}

ll cal(ll md){
    ll ans = md;
    for(ll i=0;i<n;i++)
        for(ll j=0;j<m;j++)
            vis[i][j] = 0;
    vis[x][y] = 1;
    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<pair<ll,pair<ll,ll>>>> pq;
    pq.push({0,{x,y}});
    ll dx[4] = {-1,1,0,0};
    ll dy[4] = {0,0,-1,1};
    ll arr = 0;
    while(pq.size())
    {
        auto pp = pq.top();
        pq.pop();
        if(md<pp.first)
        {
            ans += pp.first-md;
            md = pp.first;
        }
        arr +=1;
        md += pp.first;
        ll nx = pp.second.first,ny = pp.second.second;
        for(ll i=0;i<4;i++)
        {
            ll tox = dx[i]+nx;
            ll toy = dy[i]+ny;
            if(!ifon(tox,toy)) continue;
            if(vis[tox][toy]) continue;
            vis[tox][toy] = 1;
            pq.push({grid[tox][toy],{tox,toy}});
        }
    }
    return ans;
}

void solve(){
    cin>>n>>m>>x>>y;
    x--;y--;
    for(ll i=0;i<n;i++)
        for(ll j=0;j<m;j++)    
            cin>>grid[i][j];
    ll st = grid[x][y];
    grid[x][y] = 0;
    ll ans = cal(st);
    if(ans <= st){
        cout<<"No cheating need."<<endl;
    } else
        cout<<ans<<endl;
}

signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    ll t = 1;
    while(t--){
        solve();
    }
}

K

有一个点，就是如果分解质因数是后，小于n的话那么，那直接补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
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
void solve()
{
    int cnt = 0;
    int n;cin >> n;
    while(n)
    {
        if(n == 1)
        {
            cout << cnt + 1 << "\n";
            return ;
        }
        //直接秒了
        for(int i = 2; i*i<= n; i++)
        {
            int nn = n;
            int l = 1;
            if(n % i == 0)
            {
                while(nn % i == 0)
                {
                    nn /= i;
                    l *= i;
                }
                if(l + n/l <= n)
                {
                    cout << cnt + 1 << "\n";
                    return ;
                }
                //直接秒了
                else
                {
                    break;
                }
            }
        }
        //砍去一半血
        cnt++;
        n /= 2;
    }
}
 
signed main()
{
    int n;cin >> n;
    while(n--) solve();
}
img