题解记录*

一时失言乱红尘 2022-09-02 11:39 107阅读 0赞

## 百度之星二   第一题 ##

注意负数取余的过程

#include <bits/stdc++.h>
    
    using namespace std;
    
    #define LL long long
    
    const int mod = 998244353;
    
    int a, b, k;
    
    LL qmi(LL a, int b)
    { 
        LL ans = 1;
        for(;b;b>>=1,a=a*a%mod)
            if(b&1) ans = ans * a % mod;
    
        return ans;
    }
    
    int main ()
    { 
        int T;
        cin >> T;
        while (T -- )
        { 
            cin >> a >> b >> k;
    
            if (k == 0)
            { 
                cout << a << b << endl;
                continue;
            }
    
            else if(k & 1)
            { 
                k /= 2;
                cout << (LL)qmi(2,k)*(a+b)%mod << " " << (LL)qmi(2,k)*(a-b+mod)%mod << endl; 
            } 
            else
            { 
                k /= 2;
                cout << (LL)qmi(2,k)*a%mod << " " << (LL)qmi(2,k)*b%mod << endl;
            }
    
        }
        return 0;
    }

--------------------

## 第二题 ##

贪心

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 1e5 + 10;
    
    int n, k, now, cnt;
    int a[N], b[N];
    
    int main ()
    { 
        int T;
        cin >> T;
        while (T -- )
        { 
            
            cin >> n >> k;
            for (int i = 1; i <= n; i ++) 
                scanf("%d", &a[i]);
    
            sort(a+1, a+1+n);
    
            now = a[1] - k;
            b[1] = now++;
    
            for (int i = 2; i <= n; i ++)
            { 
                if (a[i] - k > now) now = a[i] - k, b[i] = now++; 
                else if (now <= a[i] + k) b[i] = now ++;
                else b[i] = now - 1;
            }
    
            cnt = 1;
            b[0] = b[1];
            for(int i = 1; i <= n; i ++)
            { 
                if(b[i] == b[i-1]) continue;
                else cnt ++;
            }
            cout << cnt << endl;
    
        }
        return 0;
    }

--------------------

## 第四题 ##

注意细节，打表，找规律

#include <bits/stdc++.h>
    
    using namespace std;
    
    #define ll long long
    
    const int N = 1e5 + 7;
    
    ll n, m, arr[N], pre[N];
    
    int main ()
    { 
    	int T;
    	cin >> T;
    	while (T -- )
    	{ 
    	    
    		cin >> n >> m;
    
    		ll f = 0, lm = 0, Max = 0, res = 0;
    
    		for(int i = 1; i <= n; i++)
    		{ 
    			scanf("%lld", &arr[i]);
    
    			pre[i] = pre[i-1] + arr[i]; // 前缀和
    			f += arr[i]; // 记录当前值
    			f = max((ll)0, f);
    
    			Max = max(Max, f); // 记录加一轮过程中出现的最大值
    			lm = max(lm, pre[i]); // 最后一轮可能出现的最大值
    
    		}
    		
    		if(Max >= m)
    		{ 
    			cout << 1 << endl;
    			continue;
    		}
    
    		if(f + Max >= m)
    		{ 
    			cout << 2 << endl;
    			continue;
    		}
    
    		if(pre[n] <= 0)
    		{ 
    			cout << -1 << endl;
    			continue; 
    		}
    
    		m -= (f + lm);  // 减去第一局和最后一局
    
    		res = m / pre[n];
    
    		if(m % pre[n]) res ++; // 如果说取模有剩下的，说明是上一步的除法是下取整的过程，需要开启下一轮
    
    		cout << res+2 << endl; // 加上开头和最后一局
    
    	}
    	return 0;
    }