哈尔滨理工大学第七届程序设计竞赛决赛（网络赛-高年级组）

哈尔滨理工大学第七届程序设计竞赛决赛（网络赛-高年级组）

A 所有情况的和

题目链接：

https://www.nowcoder.com/acm/contest/30/A

思路：

可以总结出公式：

\[ sum = \prod\limits_{i = 1}^n {(a_i + b_i)} \]

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1005;
const ll mod = 1e9+7;
ll a[maxn][2],sum,res;
int n;
int main() {
    while(~scanf("%d",&n)) {
        sum=0;
        res=1;
        for(int i=1;i<=n;++i) {
            sum=0;
            for(int j=0;j<=1;++j) {
                scanf("%lld",&a[i][j]);
                sum+=a[i][j];
            }
            res=(res%mod*sum%mod)%mod;
        }
        printf("%lld\n",res);
    }
    return 0;
}

B 幸运大奖

题目链接：

https://www.nowcoder.com/acm/contest/30/B

思路：

直接暴力枚举，注意ios::sync_with_stdio(false);的优化，不然GG

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,k;
string s,res;
ll change(string str) {
    ll ans = 0,temp=1;
    int len = str.length();
    for(int i=len-1;i>=0;--i) {
        if(str[i]=='1') ans+=temp;
        temp=temp*2;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    int cnt=1;
    while(t--) {
        cin>>k>>s;
        int len=s.length();
        res="";
        for(int j=0;j<=len-k;++j) {
            string temp=s.substr(j,k);
            if(temp.compare(res)>0) res=temp;
        }
        cout<<"Case #"<<cnt<<": "<<change(res)<<endl;
        cnt++;
    }
    return 0;
}

D 数圈圈

题目链接：

https://www.nowcoder.com/acm/contest/30/D

思路：

基本的数位DP或者找规律都可以解

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,sum,a1,a2,a3,a4,a5;
ll count(ll n, int x) {
    ll cnt=0,k;
    for (ll i=1;k=n/i;i*=10) {
        ll high=k/10;
        if(x==0) {
            if(high) high--;
            else break;
        }
        cnt+=high*i;
        ll cur=k%10;
        if(cur>x) cnt += i;
        else if(cur == x) cnt+=n-k*i+1;
    }
    return cnt;
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%lld %lld",&a,&b);
        a1=count(b,0)-count(a-1,0);
        a2=count(b,4)-count(a-1,4);
        a3=count(b,6)-count(a-1,6);
        a4=count(b,8)-count(a-1,8);
        a5=count(b,9)-count(a-1,9);
        sum=a1+a2+a3+a4*2+a5;
        cout<<sum<<endl;
    }
}

E 求最大值

题目链接：

https://www.nowcoder.com/acm/contest/30/E

思路：

要使得a[j]-a[i]尽量大，j-i尽量小。推出：只考虑相邻两者之间的差值即可。证明略（画图即可）
注意最后的rbegin()->first。如果另外开辟对象再输入，会造成只能通过66.67%的数据。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
int a[maxn];
int main() {
    int n;
    while(scanf("%d",&n)!=EOF) {
        map<int,int> mp;
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        for(int i=2;i<=n;++i) mp[a[i]-a[i-1]]++;
        int Q;scanf("%d",&Q);
        while(Q--) {
            int p,y;scanf("%d %d",&p,&y);
            if(p>1) {
                int temp=a[p]-a[p-1];
                mp[temp]--;
                if(mp[temp]==0) mp.erase(temp);
                mp[y-a[p-1]]++;
            }
            if(p<n) {
                int temp=a[p+1]-a[p];
                mp[temp]--;
                if(mp[temp]==0) mp.erase(temp);
                mp[a[p+1]-y]++;
            }
            a[p]=y;
            printf("%d.00\n",mp.rbegin()->first);
        }
    }
    return 0;
}