codeforces 466C 计数 codeforces 483B 二分 容斥

题意：给你n个数，将他们分成连续的三个部分使得每个部分的和相同，求出分法的种数。

思路：用一个数组a[i]记下从第一个点到当前i点的总和。最后一个点是总和为sum的点，只需求出总和为1/3sum的点和总和为2/3sum的点搭配的所有情况。遍历一遍总和为2/3sum的点前总和为1/3sum的点的个数。

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int MAXN=500005;
typedef long long ll;
ll a[MAXN];
int main() {
    int n;
    while(~scanf("%d",&n)) {
        a[0]=0;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            a[i]=a[i]+a[i-1];
        }
        if(a[n]%3!=0) {    
            printf("0
");
            continue;
        }
        ll sum1=a[n]/3; 
        ll sum2=sum1*2; int cn1=0;ll cut=0;
        for(int i=1;i<n;i++)
        {     
            if(a[i]==sum2 )
            {
                cut+=cn1;
            }
            if(a[i]==sum1 && i<n-1)
            {
                cn1++;
            }
        }
        cout<<cut<<endl;
    } 
    return 0;
}

 

 

 

题意：求出最小满足的数v使得在集合1,2,...,v中能找到cnt1个不能被x整除的数与cnt2个不能被y整除的数（x与y是质数）。

 

思路：考虑对任意一个数n，a=n-n/x表示不能被x整除的个数，b=n-n/y表示不能被y整除的个数，c=n-(n/x-n/x/y)-(n/y-n/x/y)-n/x/y=n-n/x-n/y+n/x/y表示既不能被x整除又不能被y整除的公共部分。

#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
    int cnt1,cnt2,x,y;
    while(cin>>cnt1>>cnt2>>x>>y)
    {
        ll l=cnt1+cnt2;
        ll r=2e18;
        ll middle=(l+r)/2;
        
        while(l<r)
        {
            ll a=middle-middle/x;
            ll b=middle-middle/y;
            ll c=middle+middle/x/y-middle/x-middle/y;
            a-=c;
            b-=c;
            if(((cnt1>a)?(cnt1-a):0)+((cnt2>b)?(cnt2-b):0)<=c)
            {
                r=middle;
            }
            else
            {
                l=middle+1;
            }
            middle=(l+r)/2;
        }
        cout<<middle<<endl;         
    }  
    return 0;
}