一类trick【鸽巢原理】

港控/mmm° 2024-03-16 16:34 13阅读 0赞

[选数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![dd403216b52045989e6391698bf4169e.png][]

思路：

给序列做个前缀和，同时模上N

如果两个位置的前缀和模N的结果相同，那么这两个位置之间的那个数模N就是0

因为模N最多只有N种情况，前缀和有N+1种情况，因此一定存在两个位置模N的结果相同

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    
    map<int,int> mp;
    
    int N;
    int a[mxn],pre[mxn];
    
    void solve(){
        cin>>N;
        for(int i=1;i<=N;i++){
            cin>>a[i];
            pre[i]=(pre[i-1]+a[i])%N;
        }
        mp[0]=0;
        for(int i=1;i<=N;i++){
            pre[i]%=N;
            if(mp.count(pre[i])){
                cout<<i-mp[pre[i]]<<'\n';
                for(int j=mp[pre[i]]+1;j<=i;j++) cout<<j<<" \n"[j==i];
                return;
            }
            mp[pre[i]]=i;
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[D - Multiple of 2019 (atcoder.jp)][D - Multiple of 2019 _atcoder.jp]

题意：

![d58389db04b9496c827788215a217b4d.png][]

思路：

同样的道理，可以给后缀和模2019，如果两个位置模2019的结果相同，那么中间那个数就一定是2019的倍数，所以可以直接map计数

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    
    map<int,int> mp;
    
    string s;
    
    void solve(){
    	cin>>s;
    	int n=s.size();
    	s=" "+s;
    	mp[0]++;
    	int d=1,now=0,ans=0;
    	for(int i=n;i>=1;i--){
    		now=(now+d*(s[i]-'0')%2019)%2019;
    		ans+=mp[now];
    		mp[now]++;
    		d=(d*10)%2019;
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/456
[dd403216b52045989e6391698bf4169e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/e0758ece0e904f418575f5e48009f01e.png
[D - Multiple of 2019 _atcoder.jp]: https://atcoder.jp/contests/abc164/tasks/abc164_d
[d58389db04b9496c827788215a217b4d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/d7dbb7b5c1cd4c7289db86a1738ac427.png