F、爱学习的小蓝

 #include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
typedef pair<int, int>PII;
#define NO {puts("No") ; return ;}
#define YES {puts("Yes") ; return ;}
//typedef long long LL;
#define int long long
const int N = 2e5 + 10, M = 2 * N;

void solve()
{
    int x;cin >> x;
    if(x <= 2)cout << 1 << endl;
    else if(x > 2 && x <= 10)cout << 2 << endl;
    else if(x > 10 && x <= 18)cout << 3 << endl;
    else if(x > 18 && x <= 36)cout << 4 << endl;
    else if(x > 36 && x <= 54)cout << 5 << endl;
    else if(x > 54 && x <= 86)cout << 6 << endl;
    else cout << 7 << endl;
}

signed main()
{
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}

A、玉米大炮

这种最优解的问题首先要考虑的问题就是二分,贪心,dp。然后我们发现答案具有二分性,时间越长我们
的答案肯定越成立

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
#define NO {puts("No") ; return ;}
#define YES {puts("Yes") ; return ;}
//typedef long long LL;
#define int long long
typedef pair<int, int>PII;
const int N = 2e5 + 10, M = 2 * N,INF = 2e9;
PII q[N];
int n,m;

bool check(int t)
{
    int sum = 0;
    for(int i = 0; i < n; i ++)
    {
        sum += (t / q[i].second) * q[i].first;
        //要及时退出防止爆LL
        if(sum >= m)break;
    }

    if(sum >= m)return true;
    return false;
}

void solve()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
    {
        int a,b;cin >> a >> b;
        q[i] = {a,b};//伤害,时间
        m -= a;
    }

    int l = 0,r = 1e18;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid))r = mid;
        else l = mid + 1;
    }

    cout << l << endl;
}

signed main()
{
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
    solve();
    return 0;
}

B、逆序对计数

问题关键:求解任意一段区间内的逆序对数量

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
#define NO {puts("No") ; return ;}
#define YES {puts("Yes") ; return ;}
//typedef long long LL;
#define int long long
typedef pair<int, int>PII;
const int N = 6010, M = 2 * N,INF = 2e9;
int a[N],tr[N],f[N][N];
int n,m;

int lowbit(int x)
{
    return x & -x;
}

void add(int x,int c)
{
    for(int i = x; i < N; i += lowbit(i))tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i))res += tr[i];
    return res;
}

//逆序对:看一个数右边有多少个比它小的
//处理出每个区间内的逆序对数量,最终的答案就是不变区间的逆序对数量加上变化区间的最大逆序对数量减去翻转前的数量
void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)cin >> a[i];

    for(int i = 1; i <= n; i ++)
    {
        //正序枚举,判断当前点前面有多少个数比它大还是小
        //若为逆序枚举,则是判断当前点后面有多少个数比它大还是小
        for(int j = i; j <= n; j ++)
        {
            int y = a[j];
            f[i][j] = f[i][j - 1] + sum(n) - sum(a[j]);//求a[j]的逆序对,还要加上前面数的逆序对才是整个区间的逆序对
            add(a[j], 1);
        }

        for(int j = i; j <= n; j ++)
            add(a[j], -1);
    }

    cin >> m;
    while(m --)
    {
        int l,r;cin >> l >> r;
        int len = r - l + 1;
        cout << f[1][n] - f[l][r] + (len - 1) * len / 2 - f[l][r] << endl;
        //例如区间长度为5,最多有4 + 3 + 2 + 1个逆序对,等差数列(n-1)*(1+n-1)/2
    }
}

signed main()
{
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
    solve();
    return 0;
}

区间操作

题目大意,给定一些操作,让一段区间乘上一个数,求出一段区间乘积的质因数的幂次之和
首先有两种思路:
1、直接用线段树模拟,我们会发现入果乘的数很多的话是会爆long long的
2、将乘看成是加,我们只维护幂次,区间乘上一个数就先将它分解质因数后加到区间内
求幂次之和就转化成了区间求和
优化:用线性筛预处理出所有的质数,然后再调用分解质因数算法

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
#define NO {puts("No") ; return ;}
#define YES {puts("Yes") ; return ;}
typedef long long LL;
#define int long long
typedef pair<int, int>PII;
const int N = 4e6 + 10, M = 2 * N, INF = 2e9;
int w[N], primes[N];
bool st[N];
int n, m, cnt;

struct Edge {
    int l, r;
    int sum, add;
} tr[N * 4];


void init() {
    for (int i = 2; i < N; i ++) {
        if (!st[i])primes[cnt ++ ] = i;

        for (int j = 0; primes[j] * i < N; j ++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)break;
        }
    }
}

int rec(int x) {
    if (x == 1)return 0;
    int res = 0;
    for (int i = 0; primes[i] * primes[i] <= x; i ++) {
        if (x % primes[i] == 0) {
            while (x % primes[i] == 0) {
                res ++;
                x /= primes[i];
            }
        }
    }

    if (x > 1)res += 1;
    return res;
}

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u) {
    if (tr[u].add) {
        tr[u << 1].add += tr[u].add, tr[u << 1].sum += tr[u].add * (tr[u << 1].r - tr[u << 1].l + 1);
        tr[u << 1 | 1].add += tr[u].add, tr[u << 1 | 1].sum += tr[u].add * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1);
        tr[u].add = 0;
    }
}

void build(int u, int l, int r) {
    if (l == r)tr[u] = {l, r, w[l], 0};
    else {
        tr[u] = {l, r, 0, 0};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int c) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].sum += c * (tr[u].r - tr[u].l + 1);
        tr[u].add += c;
    }

    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)modify(u << 1, l, r, c);
        if (r > mid)modify(u << 1 | 1, l, r, c);
        pushup(u);
    }
}

int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r)return tr[u].sum;
    else {
        pushdown(u);
        int res = 0;
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)res += query(u << 1, l, r);
        if (r > mid)res += query(u << 1 | 1, l, r);
        return res;
    }
}

void solve() {
    init();//线性筛
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int a;
        cin >> a;
        w[i] = rec(a);
    }

    build(1, 1, n);
    cin >> m;
    while (m --) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            cin >> l >> r;
            cout << query(1, l, r) << endl;
        } else {
            int l, r, c;
            cin >> l >> r >> c;
            modify(1, l, r, rec(c));
        }
    }
}

signed main() {
    //  int t;cin >> t;
    //  while(t --)
    //  {
    //      solve();
    //  }
    solve();
    return 0;
}

小蓝的新技能
$本题的要点是:gcd(a^3,b^3) = gcd(a,b)^3,lcm同理$
$我们可以先枚举gcd,由于gcd是a的最大公约数,所以还可以枚举a,时间上是可以的$
$然后求出lcm,看是否能开尽三次方,最后求出b,检验一下所有的条件看是否满足$

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
#define NO {puts("No") ; return ;}
#define YES {puts("Yes") ; return ;}
typedef long long LL;
#define int long long
typedef pair<int, int>PII;
const int N = 4e6 + 10, M = 2 * N, INF = 2e9;
int w[N], primes[N];
bool st[N];
int n, m, cnt;

int gcd(int a,int b)
{
    return b ? gcd(b,a % b): a;
}

int sqrts(int x)
{
    int l = 0,r = 1e6;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(mid * mid * mid <= x)l = mid;
        else r = mid - 1;
    }

    return l;
}

//我们枚举gcd,然后枚举a.用n-gcd得到理想的lcm
void solve() 
{
    int n;cin >> n;
    int res = 0;
    for(int d = 1; d * d * d <= n; d ++)//枚举gcd
    {
        //因为d是a的最大公约数,所以我们的第二重循环并不是O(n)的
        for(int a = d; a * a * a <= n; a += d)//枚举a(1~n之间的数)
        {
            int lcm = n - d * d * d;//三次方
            int t = sqrts(lcm);//开三次方
            if(t * t * t == lcm)//检验lcm是否正确
            {
                int b = t * d / a;//求出b的值
                if(b && gcd(a,b) == d && a * b / gcd(a, b) == t)res ++;
            }
        }
    }

    cout << res << endl;
}

signed main() 
{
    //  int t;cin >> t;
    //  while(t --)
    //  {
    //      solve();
    //  }
    solve();
    return 0;
}

旅行

每个城市都有两种选择:做核酸和不做核酸两种选择,所以考虑分层图最短路
dist[][0/1]第二维表示核酸能维持的天数
做核酸就在1上跑最短路,不做就在0上跑最短路,这样可以将所有情况都遍历到

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
#define NO {puts("No") ; return ;}
#define YES {puts("Yes") ; return ;}
typedef long long LL;
#define int long long
typedef pair<int, int>PII;
const int N = 1e5 + 10, M = 4 * N, INF = 2e9;
int h[N],e[M],ne[M],w[M],idx;
int dist[N][3];//第二维表示核酸还能用几天
bool st[N][3];
int n,m,x;

struct node
{
    int d,ver,state;
    bool operator>(const node &t)const
    {
        return d > t.d;
    }
};

void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

void dijkstra()
{
    priority_queue<node,vector<node>,greater<node>>q;
    memset(dist,0x3f,sizeof dist);
    dist[1][0] = 0;
    q.push({dist[1][0],1, 0});
    while(!q.empty())
    {
        auto t = q.top();
        q.pop();
        int ver = t.ver,distance = t.d,state = t.state;
        if(st[ver][state])continue;
        st[ver][state] = true;

        for(int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if(state == 0)
            {
                if(dist[j][1] > distance + w[i] +  x)
                {
                    dist[j][1] = w[i] + distance + x;
                    q.push({dist[j][1],j,1});
                }
            }
            else 
            {
                if(dist[j][0] > distance + w[i])
                {
                    dist[j][0] = distance + w[i];
                    q.push({dist[j][0],j,0});
                }
            }
        }
    }
}

void solve()
{
    cin >> n >> m >> x;
    memset(h,-1,sizeof h);
    for(int i = 0; i < m; i ++)
    {
        int a,b,c;cin >> a >> b >> c;
        add(a,b,c),add(b,a,c);
    }

    dijkstra();

    cout << min(dist[n][0],dist[n][1]) << endl;
}

signed main() 
{
    //  int t;cin >> t;
    //  while(t --)
    //  {
    //      solve();
    //  }
    solve();
    return 0;
}

神奇数字

假设右两个数为a,b同余于x,那么a能表示成a=q_1*x+r,b=q_2*x+r的形式。a-b=(q_1 - q_2)
可知x需要满足的条件是是(a-b)的约数即可
三个数同理求出所有的差的最大公约数,然后对其分解得到所有的约数即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>

using namespace std;
#define NO {puts("No") ; return ;}
#define YES {puts("Yes") ; return ;}
typedef long long LL;
//#define int long long
typedef pair<int, int>PII;
const int N = 1e5 + 10, M = 4 * N, INF = 2e9;
int n,m,x;

int gcd(int a,int b)
{
    return b ? gcd(b, a % b) : a;
}

void solve()
{ 
    int a,b,c;cin >> a >> b >> c;

    if(a == b && b == c)
    {
        cout << -1 << endl;
        return;
    }

    int d = 0;
    d = gcd(d, gcd(abs(a - b),abs(b - c)));
    d = gcd(d, abs(a - c));

    vector<int>s;
    for(int i = 1; i <= d / i; i ++)
    {
        if(d % i == 0) 
        {
            s.push_back(i);
            if(d / i != i)s.push_back(d / i);
        }
    }

    sort(s.begin(),s.end());
    for(auto x : s)cout << x << " ";
    cout << endl;
}

signed main() 
{
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    //solve();
    return 0;
}