上海7月月赛丙组参考代码

r囧r小猫 2023-03-01 12:41 13阅读 0赞

# 题目 #

https://iai.sh.cn/contest/7

# T1 #

#include <iostream>
    using namespace std;
    
    int main()
    { 
        int a, x, y;
        cin >> a >> x >> y;
        cout << y + x << ' ' << a * (y + x) - x;
        return 0;
    }

# T2 #

## 分析 ##

最后四个测试点，数据很大。不能用int或long long来做。  
第一步可以使用string类型。10^1000用string来表示是1000位，每位的最大数字是9，加起来最大是9000。所以从第二步开始用int就可以了。

## 代码 ##

#include <iostream>
    using namespace std;
    
    int main()
    { 
        //freopen("T2.in", "r", stdin);
    
        int n, x, t;
        cin >> n >> x >> t;
        int sum = 0, lastT = t;
        for(int i = 2; i <= n; i++)
        { 
            cin >> t;
            sum += min(x, t - lastT);
            lastT = t;
        }
        sum += x;
    
        cout << sum;
    
        return 0;
    }

# T3 #

#include <bits/stdc++.h>
    using namespace std;
    
    int getSum(int x)
    { 
        int sum = 0;
        while(x)
        { 
            sum += x % 10;
            x /= 10;
        }
    
        return sum;
    }
    
    int getRoot(int y)
    { 
        if(y < 10)
        { 
            return y;
        }
        else
        { 
            int sum = getSum(y);
            return getRoot(sum);
        }
    }
    
    int main()
    { 
        string s;
        cin >> s;
        int len = s.size();
        int sum = 0;
        for(int i = 0; i < len; i++)
        { 
            sum += s[i] - '0';
        }
    
        cout << getRoot(sum);
    
        return 0;
    }

# T4 #

## 解法一：枚举，60分 ##

#include <iostream>
    using namespace std;
    
    #define LL long long
    
    const int maxN = 10005;
    LL a[maxN];
    
    int main()
    { 
        int n, k;
        cin >> n >> k;
        for(int i = 1; i <= n; i++)
        { 
            cin >> a[i];
        }
    
        int cnt = 0;
        for(int L = 1; L <= n; L++)
        { 
            LL sum = 0;
            for(int R = L; R <= n; R++)
            { 
                sum += a[R];
                if(sum % k == 0)
                { 
                    cnt++;
                }
            }
        }
    
        cout << cnt;
    
        return 0;
    }

## 解法二 ##

### 分析 ###

用样例1中的数据来分析。  
（一）利用前缀和  
sum\[1\] = 3, sum\[2\] = 5。sum\[2\]与sum\[1\]的差是k的倍数，说明a\[2\]必然是k的倍数。sum\[3\] = 9，sum\[3\]与sum\[2\]的差是k的倍数，说明a\[3\]是k的倍数，并且a\[2\] + a\[3\]也是k的倍数。sum\[4\] = 10，说明a\[1\] + a\[2\] + a\[3\] + a\[4\]的和是k的倍数。

（二）差转化为模  
可将前缀和取模。这样sum\[1\] % k = 3 % k = 1，sum\[2\] % k = 5 % k = 1，两次和的值取模后都是1，说明a\[2\]可以被k整除。sum\[3\] % k = 9 % k = 1，第三次取模后为1，说明a\[3\]可以被k整除，并且a\[2\] + a\[3\]也能被k整除。

#include<cstdio>
    
    typedef long long LL;
    const int maxn = 2e5+5;
    LL sum[maxn], cnt[maxn], n, k;
    
    int main()
    { 
        scanf("%d%d", &n, &k);
    
        LL ans = 0;
        for(int i = 1; i <= n; i++)
        { 
            LL t;
            scanf("%lld", &t);
            sum[i] = (sum[i-1] + t) % k;
            ans += cnt[sum[i]];
            cnt[sum[i]]++;
        }
    
        printf("%lld\n", ans + cnt[0]);
    
        return 0;
    }

# T5 #

#include<bits/stdc++.h>
    using namespace std;
    
    
    #define int long long
    int n, t, a[100100], b[100100], res;
    
    signed main()
    { 
        //freopen("T5.in","r",stdin);
    
    	ios::sync_with_stdio(0);
    	cin.tie(NULL);
    	cout.tie(NULL);
    
    	cin>>n>>t;
    	for(int i=1;i<=n;i++)
        { 
            cin>>a[i];
            a[i]+=a[i-1];   //前缀和
        }
    
    	for(int i=1;i<=n;i++)
        { 
            cin>>b[i];
            b[i]+=b[i-1];   //前缀和
        }
    
    	for(int i=0;i<=n;i++)
        { 
    		if(a[i]>t)
            { 
                break;
            }
    
    		res=max(upper_bound(b+1, b+n+1, t-a[i]) - (b+1) + i, res);
    	}
    	cout<<res<<endl;
    
    	return 0;
    }

> 长按或扫描识别二维码加好友邀请进信息学竞赛群  
> ![在这里插入图片描述][20200725215229834.png]

[20200725215229834.png]: /images/20230208/8b9444fb42154e4e8e756e1d4dc1a1f3.png