牛客IOI周赛20-普及组

思路：
容易发现这个题要求的就是它的所有因子之和，所以
唯一分解定理

就可以用一个比较不错的复杂度切掉这题。
代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long int ll;
ll dcpSum(ll x){//所有因子的和（包括1）
    ll ans = 1;
    for(ll i = 2; i * i <= x; i++){
        if(x % i == 0){
            ll temp = 1;
            while(x % i == 0){
                x /= i;
                temp *= i;
            }
            ans *= (temp * i - 1) / (i - 1);//对每一个素数因子按图一公式求积。
        }
    }
    if(x > 1) ans *= (1 + x);
    return ans;
}
void solved(){
    ll n;scanf("%lld",&n);
    ll s = dcpSum(n) - n;
    /*
    ll s = 0;
    for(int i = 1; i * i <= n; i++){
        if(n % i == 0){
            s += i;
            if(i * i != n && i != 1){
                s += (n / i);
            }
        }
    }
    */
    if(s == n){
        cout << "Pure" << endl;
    }else if(s > n){
        cout << "Late" << endl;
    }else{
        cout << "Early" << endl;
    }
}
int main(){
    solved();
    return 0;
}

思路：
模拟就行了
由于会回溯到某个位置，所以用一个数组记录每一步就行了。
代码：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int maxn = 2e5 + 10;
char s[maxn];
pair<int,int>ve[maxn];
void solved(){
    int n;scanf("%d",&n);
    scanf("%s",s + 1);
    int cur = 0;
    ve[cur] = {0,0};
    for(int i = 1; i <= n; i++){
        int x = ve[cur].first;
        int y = ve[cur].second;
        if(s[i] == 'W'){
            ve[++cur] = {x,y + 1};
        }
        if(s[i] == 'A'){
            ve[++cur] = {x - 1,y};
        }
        if(s[i] == 'S'){
            ve[++cur] = {x,y - 1};
        }
        if(s[i] == 'D'){
            ve[++cur] = {x + 1,y};
        }
        if(s[i] == 'Z'){
            cur--;
            cur = max(0,cur);
        }
    }
    cout << ve[cur].first << ' ' << ve[cur].second << endl;
}
int main(){
    solved();
    return 0;
}

思路：
贪心：先把石头对剪刀，剪刀对布，布对石头，这样可以赢得到的分数是(min(a1,b2) + min(b1,c2) + min(c1,c2))*2
然后把用掉的全部剪掉，然后再取平局就好了。
代码：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long int ll;
void solved(){
    ll a1,b1,c1,a2,b2,c2;
    ll n;cin >> n;
    cin >> a1 >> b1 >> c1;
    cin >> a2 >> b2 >> c2;
    ll t1 = min(a1,b2);
    ll t2 = min(b1,c2);
    ll t3 = min(c1,a2);
    ll s = t1 * 2 + t2 * 2 + t3 * 2;
    a1 -= t1;b2 -= t1;
    b1 -= t2;c2 -= t2;
    c1 -= t3;a2 -= t3;
    s += min(a1,a2) + min(b1,b2) + min(c1,c2);
    cout << s << endl;
}
int main(){
    solved();
    return 0;
}

这题我题意理解错了，导致在错误的道路上越走越远，这题其实很简单。。。
我一开始看到这个题想到的是权值线段树，不过值域太大了，又离散化不了。就换其它方向，后面想，先对所有数排序，然后枚举每个数，二分出它的[l - x,r - x]的区间，然后求这个区间<=这个数在原序列的index的数量，这就转化为区间<=x数量问题了，可以考虑主席树搞。。。。最后没搞出来。。。我错就错在i<j这个条件没理解清楚。
其实这个题目就是要我们求任意两个数的和在[l,r]有多少个。
那么只需要排序，然后对每个数二分一下它的可以选的区间累和就完了。。。。害。。。一直卡在i<j上面了，其实换个题意就直接秒了。。。。
代码：

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int ll;
const int maxn = 2e5 + 10;
ll n,x,y;
ll a[maxn];
void solved(){
    cin >> n >> x >> y;
    for(int i = 1; i <= n; i++)cin >> a[i];
    sort(a + 1,a + 1 + n);
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        int l = lower_bound(a + 1 + i,a + n + 1,x- a[i]) - (a);
        int r = upper_bound(a + 1 + i,a + n + 1,y - a[i]) - (a);
        ans += (r - l);
    }
    cout << ans <<endl;
}
int main(){
    solved();
    return 0;
}