include [HTML_REMOVED]

define MAXn 100010

using namespace std;

int n, m;
int a[MAXn];

int ls[MAXn], ls_cnt;
map[HTML_REMOVED] LS;

struct Node
{
int l, r;
int cnt;
}tr[MAXn * 100];
int root[MAXn], idx;

int build(int l, int r)
{
int p = ++idx;
if(l == r) return p;
int mid = (l + r) >> 1;
tr[p].l = build(l, mid);
tr[p].r = build(mid + 1, r);
return p;
}

int insert(int q, int l, int r, int x)
{
int p = idx;
tr[p] = tr[q];
if(l == r)
{
tr[p].cnt;
return p;
}
int mid = (l + r) >> 1;
if(x <= mid)
tr[p].l = insert(tr[q].l, l, mid, x);
else tr[p].r = insert(tr[q].r, mid + 1, r, x);
tr[p].cnt = tr[tr[p].l].cnt + tr[tr[p].r].cnt;
return p;
}

int query(int p, int q, int l, int r, int k)
{
if(l == r)
return l;
int mid = (l + r) >> 1;
int lcnt = tr[tr[p].l].cnt - tr[tr[q].l].cnt;
if(lcnt >= k) return query(tr[p].l, tr[q].l, l, mid, k);
else return query(tr[p].r, tr[q].r, mid + 1, r, k - lcnt);
}

int main()
{
scanf(“%d%d”, &n, &m);
for(int i = 1; i <= n; i)
{
scanf(“%d”, &a[i]);
ls[i] = a[i];
}
sort(ls + 1, ls + n + 1);
ls_cnt = 1;
for(int i = 2; i <= n; i)
{
if(ls[i] != ls[ls_cnt])
{
ls[++ls_cnt] = ls[i];
}
}

//for(int i = 1; i <= ls_cnt; i++)
//    printf("%d ", ls[i]);

for(int i = 1; i <= ls_cnt; i++)
{
    LS[ls[i]] = i;
    //printf("LS[%d] = %d\n", ls[i], i);
}

root[0] = build(1, ls_cnt);

for(int i = 1; i <= n; i++)
    root[i] = insert(root[i - 1], 1, ls_cnt, LS[a[i]]);

while(m--)
{
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    printf("%d\n", ls[query(root[r], root[l - 1], 1, ls_cnt, k)]);
}

return 0;

}

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n, x, y;
ll f[10000010];

int main()
{
    cin >> n >> x >> y;
    for(int i = 1; i <= 10000000; i++)
        f[i] = 1e18;
    for(int i = 1; i <= 10000000; i++)
    {
        f[i] = min(f[i], f[i - 1] + x);
        if(i % 2 == 0) f[i] = min(f[i], f[i >> 1] + y);
        else f[i] = min(f[i], f[(i + 1) >> 1] + x + y);
    }
    cout << f[n];
    return 0;
}

#include <bits/stdc++.h>
#define MAXn 300010
using namespace std;

int n, m;
int s[MAXn << 1];
int idx;
int root[MAXn << 1];
int max_id[MAXn * 30 * 2];
int tr[MAXn * 30 * 2][2];

void insert(int i, int k, int p, int q)//第i个数，第k位，
{
    if(k < 0)
    {
        max_id[q] = i;
        return;
    }
    int v = s[i] >> k & 1;
    if(p) tr[q][v ^ 1] = tr[p][v ^ 1];
    tr[q][v] = ++idx;
    insert(i, k - 1, tr[p][v], tr[q][v]);
    max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}

int query(int root, int w, int L)
{
    int p = root;
    for(int i = 23; i >= 0; i--)
    {
        int v = w >> i & 1;
        if(max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];
        else p = tr[p][v];
    }

    return w ^ s[max_id[p]];
}

int main()
{
    scanf("%d%d", &n, &m);

    root[0] = ++idx;
    max_id[0] = -1;
    insert(0, 23, 0, root[0]);


    for(int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        s[i] = x ^ s[i - 1];
        root[i] = ++idx;
        insert(i, 23, root[i - 1], root[i]);
    }

    while(m--)
    {
        char flag;
        cin >> flag;
        if(flag == 'A')
        {
            n++;
            int x;
            scanf("%d", &x);
            s[n] = x ^ s[n - 1];
            root[n] = ++idx;
            insert(n, 23, root[n - 1], root[n]);
        }
        else
        {
            int x, l, r;
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
        }
    }

    return 0;
}

#include<bits/stdc++.h>
#define MAXn 2010
#define MAXm 100010
#define inf 2000000000
using namespace std;

int n, m, A, B;
/////////——————————heap 
int heap_size;
struct Node { double dist; int ind; }heap[MAXm << 1];
void put(Node x) {
    heap[++heap_size] = x;
    int now = heap_size;
    while(now > 1) {
        int fa = now >> 1;
        if(heap[fa].dist > heap[now].dist) return;
        swap(heap[fa],heap[now]); 
        now = fa;
    }
    return;
}

void del() {
    heap[1] = heap[heap_size--];
    int now = 1;
    while(now*2 <= heap_size) {
        int child = now << 1;
        if(child < heap_size && heap[child].dist < heap[child+1].dist) child++;
        if(heap[now].dist >= heap[child].dist) return;
        swap(heap[now], heap[child]);
        now = child;
    }
    return;
}

inline Node get() { return heap[1];} 
////////////———————————— 

///////////—————————————Edge 
struct Edge { int to, next; double w; }e[MAXm << 1];
int e_size, head[MAXn];

void add(int u, int v, double w) {
    e[++e_size].to = v;
    e[e_size].w = w;
    e[e_size].next = head[u];
    head[u] = e_size;
    return;
}

void add_edge() {
    for(int i = 1; i <= m; i++) {
        int u, v;
        double w;
        scanf("%d%d%lf", &u, &v, &w);
        add(u, v, (100 - w) / 100);
        add(v, u, (100 - w) / 100);
    }
    return;
}
//////////——————————————

//////////——————————————
double dis[MAXn];
int vis[MAXn];

void pre_dis()
{
    for(int i = 1; i <= n; i++)
        dis[i] = 0;
    return;
}

void dijkstra(int start)
{
    pre_dis();
    dis[start] = 1;
    Node x;
    x.dist = 1;
    x.ind = start;
    put(x);
    while(heap_size > 0)
    {
        Node tmp = get();
        del();
        if(vis[tmp.ind])
            continue;
        vis[tmp.ind] = 1;
        for(int i = head[tmp.ind]; i; i = e[i].next)
        {
            if(dis[e[i].to] < dis[tmp.ind] * e[i].w)
            {
                dis[e[i].to] = dis[tmp.ind] * e[i].w;
                //cout << "tmp.ind=" << tmp.ind << endl;
                //cout << "dis[" << e[i].to <<"]=" << dis[e[i].to] << endl;
                if(!vis[e[i].to])
                {
                    x.dist = dis[e[i].to];
                    x.ind = e[i].to;
                    put(x);
                }
            }
        }
    }

    return;
}
///////////////———————————— 

void input()
{
    scanf("%d%d", &n, &m);
    add_edge();
    scanf("%d%d", &A, &B);
    return;
}

void putout()
{
    printf("%.8lf", 100 / dis[B]);

    return;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    input();
    dijkstra(A);
    putout();

    return 0;
}

__int128一种变量类型，最多128位，即范围最大到$2^{128}-1$。
注意：__int128只能进行四则运算，不能用cin和cout来输出（本蒟蒻在此不做解释），不能用位运算来定义最大值。

输入输出模板（与快读相同只是类型不同）：

//输入
inline __int128 read()
{
    __int128 num = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
            w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        num = num * 10 + ch - '0';
        ch = getchar();
    }
    return num * w;
}

//输出
inline void print(__int128 x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

下面是本题代码

#include <bits/stdc++.h>
using namespace std;

__int128 a, b, p;

inline __int128 read()
{
    __int128 num = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
            w = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        num = num * 10 + ch - '0';
        ch = getchar();
    }
    return num * w;
}

inline void print(__int128 x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

int main()
{
    a = read();
    b = read();
    p = read();
    print(a * b % p);

    return 0;
}

同步更新于我的博客
点个赞吧~

题目描述

金明有 n 天假期，编号 1 ∼ n。

整个假期期间，他每天只可能有三种选择：

去健身房健身一整天。（前提是当天健身房开放）
去图书馆看书一整天。（前提是当天图书馆开放）
在家休息一整天。

用一个长度为 n 的整数数组 a1,a2,…,an 来表示这 n 天健身房与图书馆的开放情况，其中：

$a_i$ 等于 0 表示第 i 天健身房关闭且图书馆关闭。
$a_i$ 等于 1 表示第 i 天健身房关闭但图书馆开放。
$a_i$ 等于 2 表示第 i 天健身房开放但图书馆关闭。
$a_i$ 等于 3 表示第 i 天健身房开放且图书馆开放。

金明希望自己用来休息的天数尽可能少，但是，他一定不会连续两天（或更多天）去健身房健身，也一定不会连续两天（或更多天）去图书馆看书。

请你计算，金明用来休息的最少可能天数。

$1 \le n \le 100,0 \le a_i \le 3$

题目分析

一眼的状态机DP。

设f[i][j]表示第 i 天状态是 j 时（0 – 休息，1 – 去图书馆， 2 – 去健身房），前 i 天出去的天数。

当第 i 天在家休息时，f[i][0]继承前一天的最大值即max(f[i - 1][0], f[i - 1][1], f[i - 1][2])。

当第 i 天去图书馆时，f[i][1]是前一天在家休息或去健身和钱两天去图书馆中的最大值再加 1 ，因为这一天出去了，即max(f[i - 1][0], f[i - 2][1], f[i - 1][2])。

当第 i 天去健身房时于去图书馆同理即max(f[i - 1][0], f[i - 1][1], f[i - 2][2])。

这里有一个问题，如果上一天图书馆或健身房不开，这一天的这个状态怎么办呢，我们不用管他，因为没有开放的话就不用更新答案，在下一次使用时就为 0 ，不影响结果

代码

#include <bits/stdc++.h>
using namespace std;

int n;
int a[100], f[100][3];//在家，图书馆，健身房

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d\n", &a[i]);
    for(int i = 1; i <= n; i++)
    {
        f[i][0] = max(max(f[i - 1][0], f[i - 1][1]), f[i - 1][2]);
        if(a[i] == 1) f[i][1] = max(max(f[i - 1][0], f[i - 2][1]), f[i - 1][2]) + 1;
        if(a[i] == 2) f[i][2] = max(max(f[i - 1][0], f[i - 2][2]), f[i - 1][1]) + 1；
        if(a[i] == 3)
        {
            f[i][1] = max(max(f[i - 1][0], f[i - 2][1]), f[i - 1][2]) + 1;
            f[i][2] = max(max(f[i - 1][0], f[i - 2][2]), f[i - 1][1]) + 1;
        }
    }

   printf("%d", n - max(max(f[n][0], f[n][1]), f[n][2]));

    return 0;
}

同步更新于我的博客

题目描述

给定一个平面。

平面中有 n 条与 x 轴平行的有向边，从上到下依次编号为 1 ~ n ，每条边都无限长，且两两不重合。

平面中有 m 条与 y 轴平行的有向边，从左到右依次编号为 1 ∼ m ，每条边都无限长，且两两不重合。

这些边一共有 n × m 个交点。

给定每条边的具体方向，请你判断这 n × m 个交点是否满足：从任意交点出发可以到达任意其它交点。

$2 \le n,m \le 20$

做法分析

首先先对样例1进行一个图的画，我们得到下图：

发现一点，其实最终我们需要的就只有围成的一个矩形。

先进行矩形的四个角的讨论，也就是先讲问题简化成只有两条竖线两条横线的情况。只有两种情况能够满足：四条线围成的矩形顺时针或逆时针连通，也就是下图两种情况：

所以我们得到了答案成立的初步条件，即上面的两种情况。

然后发现这两种情况与答案满足是等价的：因为对于任意一个点，我们可以先沿着所在边的方向，到达最外圈，然后就可以通过这一圈到大任意一条边的入口，从而到达任意一点。

代码

#include <bits/stdc++.h>
#define MAXn 50
using namespace std;

int n, m;
char a[MAXn], b[MAXn];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= m; i++)
        cin >> b[i];

    if(a[1] == '>' && a[n] == '<' && b[1] == '^' && b[m] == 'v')//顺时针
    {
        printf("YES\n");
        return 0;
    }
    if(a[1] == '<' && a[n] == '>' && b[1] == 'v' && b[m] == '^')//逆时针
    {
        printf("YES\n");
        return 0;
    }
    printf("NO\n");//都不符合输出NO

    return 0;
}

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;

__int128 a, b, p;

inline __int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}

int main()
{
    a = read();
    b = read();
    p = read();
    print(a * b % p);

    return 0;
}

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll a, b;
ll p;

ll mi(ll a, ll b)
{
    ll res = 1 % p;
    while(b)
    {
        if(b & 1) res = (res * a) % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    cin >> a >> b >> p;
    cout << mi(a, b);


    return 0;
}

同步更新于我的博客
点个赞再走呗~

题目描述

给定一个整数$x$，请你找到严格大于$x$且各位数字均不相同的最小整数$y$。

$1000 \le x \le 9000$

做法分析

发现数据范围很小，那么我们可以直接从$x+1$进行枚举，同时使用一个 check 函数检查是否满足条件。

代码

#include <bits/stdc++.h>
using namespace std;

int x;

bool check(int a)
{
    int num[10];//0-9每一个数字是否出现过
    for(int i = 0; i < 10; i++)
        num[i] = 0;//初始化全部没出现过
    while(a > 0)
    {
        if(num[a % 10])
            return 0;//个位数出现过，返回不成立
        num[a % 10]++;
        a /= 10;//往后缩一位
    }
    return 1;//坚持到了最后，说明符合条件
}

int main()
{
    scanf("%d", &x);
    for(int i = x + 1; ; i++)
    {
        if(check(i))//如果符合
        {
            printf("%d", i);
            return 0;//输出并返回
        }
    }

    return 0;
}