筑梯杯郑州轻工业大学第十七届程序设计大赛（同步赛）

No idea

字符串查找替换，开始用 find 交两发全 t，乖乖手写一发。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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

void solve(){
    string s;
    cin>>s;
    for(int i=0;i+3<s.size();i++){
        if(s.substr(i,4)=="2024"){
            s[i+3]='5';
        }
    }
    cout<<s<<endl;
}

int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

超椭圆

逆天签到题，开始用 pow 微分没过，以为思路不对。赛后看才发现已经过了 97.8 了，极小数的时候分的太少了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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

void solve(){
    double a,b,n;
    cin>>a>>b>>n;
    double ans=0,t=a/1e6;
    for(double i=0;i<=a;i+=t){
        ans+=t*(b*pow(1-pow(i/a,n),1.0/n));
    }
    printf("%.6lf",ans*4);
}

int main(){
    int t=1;
//     cin>>t;
    while(t--)solve();
    return 0;
}

双影奇境

观察易发现，两人和终点都在一个联通块时才能胜利，同时要求一起到，那么二者到中点的最短距离奇偶性应该一致，因为可以在路上刷步数。

同时注意某人到终点，游戏立刻结束，如果有人到终点的步数为 1，但是另一个人更大，同时这个人只有 1 这一条路能走，同样为 No。

 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


#include <bits/stdc++.h>
using namespace std;
const int N = 507;

int n,m,mp[N][N],fa[N][N],vis[N][N];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
char x;

void dfs(int x,int y,int col){
    if(x<1 || x>n || y<1 || y>m || vis[x][y] || mp[x][y]==1) return;
    vis[x][y]=1;
    fa[x][y]=col;
    for(int i=0;i<4;i++) dfs(x+dx[i],y+dy[i],col);
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>x;
            if(x=='.')mp[i][j]=0;
            else mp[i][j]=1;
        }
    }
    int tot=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!vis[i][j] && mp[i][j]==0)
                dfs(i,j,++tot);
        }
    }
    int q;
    cin>>q;
    while(q--){
        int s[3][2],tmp[2];
        for(int i=0;i<3;i++){
            cin>>s[i][0]>>s[i][1];
        }
        tmp[0]=abs(s[0][0]-s[2][0])+abs(s[0][1]-s[2][1]);
        tmp[1]=abs(s[1][0]-s[2][0])+abs(s[1][1]-s[2][1]);
        bool flag=0;
        if((tmp[0]+tmp[1])&1||(fa[s[0][0]][s[0][1]]!=fa[s[1][0]][s[1][1]])||(fa[s[2][0]][s[2][1]]!=fa[s[1][0]][s[1][1]]))flag=1;
        else{
            if(tmp[0]!=tmp[1]&&(tmp[0]==1||tmp[1]==1)){
                int id=0;
                if(tmp[1]==1)id=1;
                flag=1;
                int cnt=0;
                for(int i=0;i<4;i++){
                    if(s[id][0]+dx[i]<1 || s[id][0]+dx[i]>n || s[id][1]+dy[i]<1 || s[id][1]+dy[i]>m ) continue;
                    if(mp[s[id][0]+dx[i]][s[id][1]+dy[i]]==0)cnt++;
                }
                if(cnt>1)flag=0;
            }
        }
        if(flag)cout<<"No\n";
        else cout<<"Yes\n";
    }
}

int main(){
    int t=1;
//     cin>>t;
    while(t--)solve();
    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


#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+7;

int q;
deque<int>dq;

void solve(){
    cin>>q;
    while(q--){
        int op;
        cin>>op;
        if(op==3){
            int mid = dq.size() / 2;
            cout<<dq[mid]<<endl;
            auto it = dq.begin() + mid;
            dq.erase(it);
        }
        else {
            int val;
            cin>>val;
            if(op==2){
                dq.push_front(val);
            }
            else dq.push_back(val);
        }
    }
}

int main(){
    int t=1;
//     cin>>t;
    while(t--)solve();
    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


#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+7;

struct Node{
    int a,b,id;
    bool operator<(const Node &t)const{
        return a<t.a;
    }
}a[N];

int n,ans[N];

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].a;
    for(int i=1;i<=n;i++){
        cin>>a[i].b;
        a[i].id=i;   
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        ans[a[i].id]=max(0,2*a[i].b-i+1);
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}

int main(){
    int t=1;
//     cin>>t;
    while(t--)solve();
    return 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
38
39
40
41
42
43
44
45


#include <bits/stdc++.h>
using namespace std;
const int N=1e5+6;

struct Node{
    int u,v,w;
}e[N];

int n;
vector<int>E[N];

void solve(){
    cin>>n;
    Node ans=(Node){0,0,-1};
    for(int i=1;i<n;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
        E[e[i].u].push_back(e[i].v);
        E[e[i].v].push_back(e[i].u);
        if(e[i].w>ans.w)ans=e[i];
    }
    int x=0,y=ans.u;
    for(auto t:E[ans.v]) {
        if(t!=ans.u&&t!=ans.v) {
            x=t;
            break;
        }
    }
    if(!x) {
        y=ans.v;
        for(auto t:E[ans.u]) {
            if(t!=ans.u&&t!=ans.v) {
                x=t;
                break;
            }
        }
    }
    cout<<x<<" "<<y<<" 0\n";
    for(int i=1;i<=n;i++)E[i].clear();
}

int main(){
    int t;
    cin>>t;
    while(t--)solve();
}

ARK no NIGHTS

字符串吃史题，队长一发过了

 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


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const double d=3e-6,eps=1e-8;
int tim[3][8],day[20]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int exc(string s)
{
	int x=0;
	for(int i=0;i<s.length();++i) {
		x=x*10+s[i]-'0';
	}
	return x;
}
int Get(int y,int m)
{
	if(m!=2)  return day[m];
	int x=day[m];
	if(y%4==0)  ++x;
	return x;
}
bool check()
{
	for(int i=1;i<=6;++i) {
		if(tim[1][i]<tim[2][i])  return 0;
		else if(tim[1][i]>tim[2][i])  return 1;
	}
	return 1;
}
void solve()
{
	string s;
	for(int i=2;i>=1;--i) {
		string s;
		cin>>s;
		tim[i][1]=exc(s.substr(0,4));
		for(int j=2,now=5;j<=6;++j,now+=3)  tim[i][j]=exc(s.substr(now,2));
	}
	tim[2][4]+=8;
	if(tim[2][4]>=24) {
		tim[2][4]-=24;
		++tim[2][3];
		if(tim[2][3]>Get(tim[2][1],tim[2][2])) {
			tim[2][3]=1;
			++tim[2][2];
			if(tim[2][2]>12) {
				tim[2][2]=1;
				++tim[2][1];
			}
		}
	}
	if(check())  printf("Yes\n");
	else  printf("No\n");
}
int main()
{
	ios::sync_with_stdio(0);
	std::cin.tie(0);
	int T=1;
	cin>>T;
	while(T--) {
		solve();
	}
}

割方术

GCD 各边

 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>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y)
{
	if(!x||!y)  return x+y;
	return gcd(y,x%y);
}
void solve()
{
	ll N,M,n,m;
	cin>>N>>M>>n>>m;
	ll ans=gcd(n,gcd(m,gcd(N-n,M-m)));
	printf("%lld\n",ans);
	
}
int main()
{
	ios::sync_with_stdio(0);
	std::cin.tie(0);
	int T=1;
	cin>>T;
	while(T--) {
		solve();
	}
}

#define int bigint

参考题解：

先不考虑 $a$ 的计算, 单独考虑对于一个大整数 $x$, $\lfloor \frac{x}{b} \rfloor$ 对 $10^9+7$ 取模后如何处理.
令 $P = 10^9+7$, 有 $\lfloor \frac{x}{b} \rfloor \bmod P = (x \bmod P - x \bmod b) \bmod P \times \text{inv}(b)$
因此只需要得到 $a \bmod P$ 与 $a \bmod 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
32
33
34
35
36
37
38
39


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7, MOD = 1e9+7;

int n,b,p[N],e[N];

ll qpow(ll a,ll b,ll mod){
    ll res=1;
    while(b){
        if(b&1) res=(res*a)%mod;  
        a=(a*a)%mod;            
        b>>=1;
    }
    return res;
}

void solve(){
	cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i]>>e[i];
    }
    cin>>b;
    ll t=1,tmp=1;
    for(int i=1;i<=n;i++){
        t=t*qpow(p[i],e[i],MOD)%MOD;
        tmp=tmp*qpow(p[i],e[i],b)%b;
    }
    cout<<(t-tmp+MOD)%MOD*qpow(b,MOD-2,MOD)%MOD<<endl;
}
int main(){
	ios::sync_with_stdio(0);
	std::cin.tie(0);
	int T=1;
// 	cin>>T;
	while(T--) {
		solve();
	}
}