NOIP提高班题目汇总

coduck

1-POJ 1958 Strange Towers of Hanoi

链接

2-luogu 1226

https://www.luogu.com.cn/problem/P1226

3-nowcoder 2019河北省大学生程序设计竞赛（重现赛）b

https://ac.nowcoder.com/acm/contest/903/B

3.1题意

求$\sum_{i=1}^nq^i\ mod \ p\ \ \ q,n\leq q10^9$

3.2题解

直接等比数列求和公式?p不一定微素数
分治

3.3代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int long long 
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int ksm(int a,int b,int mod) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int solve(int n,int q,int mod) {
    if (n == 1) return q % mod;
    int tmp = solve(n / 2, q, mod);
    if (n % 2 == 0) {
        return (tmp + tmp * ksm(q, n / 2, mod)) % mod;
    }
    else {
        return (tmp + tmp * ksm(q, n / 2, mod) + ksm(q, n, mod)) % mod; 
    }
}
signed main(){
    int T = read();
    while (T -- ) {
        int q = read(), n = read(), mod = read();
        cout << solve(n, q, mod) << "\n";
    }
    return 0;
}

luogu 2044

https://www.luogu.com.cn/problem/P2044

luogu 3197

https://www.luogu.com.cn/problem/P3197

luogu 1498
https://www.luogu.com.cn/problem/P1498

P1010 [NOIP1998 普及组] 幂次方

https://www.luogu.com.cn/problem/P1010

P3612 [USACO17JAN]Secret Cow Code S

https://www.luogu.com.cn/problem/P3612

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int long long 
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
signed main(){
    string s;
    cin >> s;
    int n;
    cin >> n;
    int m = s.size(), t = m;
    while (m <= n) m *= 2; m /= 2;
    while (n > t) {
        if (n > m) {
            n -= (m + 1);
            if (n == 0) n = m;
        }
        m /= 2;
    } 
    cout << s[n - 1];
    return 0;
}

https://www.luogu.com.cn/problem/P5657
https://www.luogu.com.cn/problem/P1228
https://www.luogu.com.cn/problem/P1115
https://www.luogu.com.cn/problem/P1177
https://www.luogu.com.cn/problem/P1908
https://www.luogu.com.cn/problem/P1309
https://www.luogu.com.cn/problem/P1177
https://www.luogu.com.cn/problem/P1923

P1429 平面最近点对（加强版）

https://www.luogu.com.cn/problem/P1429

洛谷 1608 路径统计

https://www.luogu.com.cn/problem/P1608
洛谷 1144 最短路计数

HDU 6331 Walking Plan

洛谷 2865 [USACO06NOV] 路障 & 洛谷 3953 [NOIP2017] 逛 公园
CF567E President and Roads
洛谷 6175 无向图的最小环问题
洛谷 1119 灾后重建
洛谷 5651 基础最短路练习题
CF954D Fight Against Traffic
CF1076D Edge Deletion
CF715B Complete The Graph
[SDOI2009]Elaxia 的路线
[Violet 6] 故乡的梦 b & 洛谷 2685 [TJOI2012] 桥 & CF1163F Indecisive Taxi Fee
[Usaco2009 Jan] 安全路经 Travel
POJ 2395 Out of Hay & LOJ 137 最小瓶颈路加强版
AtCoder2643 Built?
AtCoder2134 Zigzag MST
BZOJ4973 比特战争
洛谷 2619/BZOJ2654 Tree
▶ FZU2087 统计树边
▶ FZU2087 统计树边
[JSOI2008] 最小生成树计数
URAL1416 Confidential
[BJWC2010] 严格次小生成树
洛谷 5540 最小乘积生成树
洛谷 4768 [NOI2018] 归程
CF609E Minimum spanning tree for each edge
HDU4126 Genghis Khan the Conqueror
BZOJ2238 Mst
BZOJ2561 最小生成树
[SHOI2010] 最小生成树