完全数

  1. 完全数满足：一个数的所有因子之和 - 它自己 = 它自己
  2. 因子之和 = 约数之和
  3. 求一个数的所有约数之和:
    先把每个质因数从0次幂一直加到其最高次幂,再把每个相应质因数幂的和相乘.

代码如下：

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)
#define endl "\n"

ll n;
unordered_map<int,int > primes;
ll ans = 1;

void divide(ll n){
    for(ll i = 2; i <= n/i; i ++ ){
        while(n % i == 0){
            n/=i;
            primes[i] ++;
        }
    }
    if(n > 1) primes[n] ++;
} 
int main() {
    cin >> n;
    divide(n);
    for(auto prime:primes){
        ll p = prime.first,a = prime.second;
        ll t = 1;
        while(a -- ) t = t * p + 1;
        ans *= t;
    }
    if(ans - n == n) cout<<"Pure";
    else if(ans - n > n) cout<<"Late";
    else cout<<"Early";                
    return 0;
}

移动撤销

  1. 利用栈来存放上一次操作
  2. 若栈不为空，就可以撤销

代码如下:

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)
#define endl "\n"

const int N = 1e5 + 10;

int n;
string s;
int x,y;
int stk[N],tt;

int main() {
    cin >> n >> s;
    int len = s.size();
    for(int i = 0; i < len; i ++ ){
        if(s[i] == 'W') y ++,stk[++ tt] = 1;
        if(s[i] == 'A') x --,stk[++ tt] = 2;
        if(s[i] == 'S') y --,stk[++ tt] = 3;
        if(s[i] == 'D') x ++,stk[++ tt] = 4;
        if(s[i] == 'Z'){
            int t = 0;
            if(tt) t = stk[tt --];
            if(t == 1) y --;
            if(t == 2) x ++;
            if(t == 3) y ++;
            if(t == 4) x --;
        }
    }
    cout<<x<<" "<<y;                
    return 0;
}

石头剪刀布

贪心策略:先把所有可能胜出的情况进行枚举，然后考虑平局的情况

代码如下:

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)
#define endl "\n"

const int N = 10;

int n;
ll a[N],b[N];
ll ans;
//每局胜者得2分，平局双方各得1分，败者不得分

int main() {
    cin >> n;
    for(int i = 0; i < 3; i ++ ){
        cin >> a[i];
    }
    for(int i = 0; i < 3; i ++ ){
        cin >> b[i];
    }
    ll x = 0;
    x = min(a[0],b[1]);
    ans += x * 2;
    a[0] -= x;
    b[1] -= x;
    x = min(a[1],b[2]);
    ans += x * 2;
    a[1] -= x;
    b[2] -= x;
    x = min(a[2],b[0]);
    ans +=  x * 2;
    a[2] -= x;
    b[0] -= x;

    ans += min(a[0],b[0]);
    ans += min(a[1],b[1]);
    ans += min(a[2],b[2]);
    cout<<ans;                    
    return 0;
}

夹缝中求和

  1. n的范围在[2,1e5]，时间复杂度O(n)或者O(nlogn)
  2. 选取一个数ai，另一个数一定在[x - ai,y - ai]之间
  3. 先进行排序，再进行二分查找不小于当前值作为左端点l，大于当前值作为右端点r
  4. 符合答案的区间为r - l.

代码如下:

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)
#define endl "\n"

const int N = 1e5 + 10;

ll n,x,y;
ll a[N];
int l,r;
ll ans;

int main() {
    cin >> n >> x >> y;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i ++ ){
        l = lower_bound(a + i + 1,a + n + 1,x - a[i]) - a;
        r = upper_bound(a + i + 1,a + n + 1,y - a[i]) - a;
        ans += (r - l);
    }
    cout<<ans;                
    return 0;
}