08-11 19:41 已编辑长春理工大学 C++ 发布于吉林

关注

题解

A 斐波那契的奥秘

血签, 直接输出第 n 项斐波那契数的平方即可, 注意取模

const int mod=1e9+7;
int n;
int f[1010];
void solve()
{
    cin>>n;
    f[1]=f[2]=1;
    for(int i=3;i<=n;i++){
        f[i]=(f[i-1]+f[i-2])%mod;
    } 
    cout<<f[n]*f[n]%mod<<endl;
}

B 秘境解码

这是一个扫描线板子题

代码：

#include<bits/stdc++.h>
#define in read()
#define MAXN 1000500
#define lson (p<<1)
#define rson (p<<1|1)
#define int long long
using namespace std;

struct SegmentTree{
	int l,r,sum,len;
}t[MAXN<<2];

struct ScanLine{
	int l,r,h;
	int mark;
	bool operator < (const ScanLine &rhs) const {
		return h<rhs.h;
	}
}L[MAXN<<1];

int n,X[MAXN<<1],ans=0;

inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}

void pushup(int p) {
	int l=t[p].l,r=t[p].r;
	if(t[p].sum)t[p].len=X[r+1]-X[l]; /* 也就是说被覆盖过 */      
	else t[p].len=t[lson].len+t[rson].len;
}

void update(int p,int ll,int rr,int mark){
	int l=t[p].l,r=t[p].r,mid=(l+r)/2;
	if(X[r+1]<=ll or rr<=X[l])return;
	if(ll<=X[l] and X[r+1]<=rr){
		t[p].sum+=mark;
		pushup(p);
		return;
	}
	update(lson,ll,rr,mark);
	update(rson,ll,rr,mark);
	pushup(p);
}

void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r)return;
	int mid=(l+r)/2;
	build(lson,l,mid);
	build(rson,mid+1,r);
	return;
}

signed main(){
	n=in;
	for(int i=1;i<=n;i++){
		int a=in,c=in,b=in,d=in;
		X[2*i-1]=a,X[2*i]=c;
		L[2*i-1]=(ScanLine){a,c,b,1};
		L[2*i]=(ScanLine){a,c,d,-1};
	}
	n<<=1;
	sort(X+1,X+n+1);
	sort(L+1,L+n+1);
	int tot=unique(X+1,X+n+1)-X-1;
	build(1,1,tot-1);
	for(int i=1;i<n;i++){
		update(1,L[i].l,L[i].r,L[i].mark);
		ans+=t[1].len*(L[i+1].h-L[i].h);
	}
	cout<<ans<<'\n';
	return 0;
}

C 小刻的字符串

易知一个字符串最长的前缀，肯定是从某位置L的字符开始连续到某位置R的字符结束。因此对于每个后缀 $A_i$ ，我们已知要求的最长前缀的左端点（起始点）为 $i$ ，二分其右端点(终点）最长可以到哪即可。

check函数即为该后缀 $A_i$ 的当前前缀子串能否在B中匹配即可，我们可以使用KMP来解决该问题。

注：解决匹配问题的方法有很多种。但如果你使用哈希可能会在计算结果上产生一些偏差导致无法通过，故更推荐不用哈希解决。

STD:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e6+10 ;
int n, m;
string str1,str2;
ll nex[N];
void KMP(string t,ll len)
{
    ll j=0;
    nex[0]=0;
    for(int i=1; i<len; i++)
    {
        while(j>0&&t[i]!=t[j]) j=nex[j-1];
        if(t[j]==t[i]) j++;
        nex[i]=j;
    }
}
bool check(ll len,string s)
{

    int j=0;
    for (int i=0; i<m; i++)
    {
        while(j>0&&str2[i]!=s[j])
        {
            j=nex[j-1];
        }
        if(str2[i]==s[j])
        {
            j++;
        }
        if(j==len)
        {
            return 1;
        }
        if(j>len) return 0;
    }
    return 0;
}
int main()
{
    cin>>n>>m;
    cin>>str1;
    cin>>str2;
    for(int i=0; i<n; i++)
    {
        ll l=i,r=n-1;
        ll ans=-1;
        while(l<=r)
        {
            ll mid=(l+r)>>1;
            string s=str1.substr(i,mid-i+1);
            KMP(s,(mid-i+1));
            if(check((mid-i+1),s)) l=mid+1,ans=mid;
            else r=mid-1;
        }
        if(ans!=-1) cout<<ans-i+1<<" ";
        else cout<<0<<" ";
    }
    return 0;
}

D LH 想吃纸杯蛋糕

题意: 找出数字串中最多的为 $x%9==0$ 的不重叠个数

方法 1

考虑 DP.

用dp[i]表示到第 i 位, 合法串的个数.

转移方程就是dp[i] = max(dp[i], dp[i - j] + s[i-j+1 ~ j]是否合法);

注意到第二重循环最多往前看 9 位, 直接 $n^2$ 转移.

bool is(string s) {
    int ans = 0;
    for (auto c : s) {
        ans *= 10;
        ans += c - '0';
        ans %= 9;
    }
    return !!!(ans % 9);
}
signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    string s;
    cin >> s;

    int n = s.size();
    s = ' ' + s;
    vector<int>dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1];
        for (int j = 1; i - j + 1 >= 1; ++j) {
            if (dp[i - j] + 1 <= dp[i])break;
            dp[i] = max(dp[i], dp[i - j] + (is(s.substr(i - j + 1, j)) ? 1 : 0));
        }
    }

    cout << dp[n] << endl;
}

方法二

考虑前缀和加双指针

用前缀和数组pre记录数字串的前缀和

用 $l,r$ 指针遍历, 当到每一个 $r$ 时, 查询 $l$ 到 $r$ 是否有 $pre[i]$ 使得 $pre[i]$ 和 $pre[r]$ 同余于 $9$ ,有就把 $l$ 挪到 $i 1$ , 答案加一

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    string s;
    cin >> s;

    int n = s.size(), ans = 0, last = 0;
    s = ' ' + s;

    vector<int>vis(10, 0);
    int l = 0;
    for (int i = 1; i <= n; ++i) {
        last = (last + s[i] - '0') % 9;
        if (vis[last] || !last) {
            ans++;
            fill(vis.begin(), vis.end(), 0);
            l = i + 1;
            last = 0;
        }
        else {
            vis[last] = i;
        }
    }

    cout << ans << endl;
}

LZ同学势必拿下XCCC全宇宙每个赛站的冠军，但秉承这节约和省时的良好习惯，LZ同学决定从1站点到n站点的过程中花费不超过 $k$ 点宇宙币的同时尽可能的节约时间，在站点之间有虫洞可供穿梭，不同虫洞需要花费 $w_{u,v}$ 点时间和 $t_{u,v}$ 点宇宙币，但是LZ同学很懒，你能帮他算出他在 $k$ 点宇宙币以内最快到达 $n$ 站点所需要的时间吗，如果LZ同学不能在 $k$ 点宇宙币以内到达 $n$ 站点，请输出“impossible”

第一行输入 $k,n,m(0 \le k \le 10000,2 \le n \le 100,1 \le m \le 10000)$ ， $k$ 表示LZ同学所能花费的最多宇宙点， $n$ 表示赛站总数， $m$ 表示虫洞总数

接下来 $m$ 行每行有 $u,v,w_{u,v},t_{u,v}(1 \le u,v \le n,1 \le w_{u,v} \le 100 ,0 \le t_{u,v} \le 100)$ ，表示 $u$ 到 $v$ 之间有一个虫洞，花费 $w_{u,v}$ 时间和 $t_{u,v}$ 点宇宙币

请注意，不同的虫洞可能有相同的出发城市和目的地城市

如果LZ同学可以到达，输出LZ同学所需要的最短时间，否则输出“impossible”

题解：

DFS or 最短路

DFS

直接搜索，存取当前的距离和花费，直接寻找即可

#include<bits/stdc++.h>

using i64 = long long;
#define inf 0x3f3f3f3f

int k, n, m;
int ans = inf;

std::vector<std::pair<int,std::pair<int,int>>> e[105];
int vis[105];

void dfs(int u, int f, int sum, int now) {
    if (sum > ans) return;
    if (u == n) {
        ans = std::min(ans, sum);
        return;
    }
    for (auto it : e[u]) {
        int v = it.first;
        int w = it.second.first;
        int t = it.second.second;
        if (v == f) continue;

        if (now - t >= 0 && !vis[v]) {
            vis[v] = 1;
            dfs(v, u, sum + w, now - t);
            vis[v] = 0;
        }
    }
}

void solve() {
    std::cin >> k >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w, t;
        std::cin >> u >> v >> w >> t;
        e[u].push_back({v, {w, t}});
    }

    vis[1] = 1;
    dfs(1, 0, 0, k);

    if (ans != inf)
        std::cout << ans << '\n';
    else 
        std::cout << "impossible" << '\n';
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    i64 t = 1;
    // std::cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

Djk

djk需要维护二维最短距离，第一维存到某个点，第二维存取花费

// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofrrst","inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define ull unsigned long long
#define ll __int128_t
#define debug(x) cout<<#x<<"="<<x<<endl;
#define fre freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
mt19937 rd(chrono::system_clock::now().time_since_epoch().count());
const int mod=998244353;
const int inf=0x3f3f3f3f3f3f3f3f;
const int MAXN=2e5+10;
const double eps=1e-6;
const int hash_p1=1610612741;
const int hash_p2=805306457;
const int hash_p3=402653189;
const int base_1=131;
const int base_2=13331;

struct edge {
    int v, w, t;
    edge(){};
    edge(int v,int w,int t):v(v),w(w),t(t){};
};

struct node {
    int dis, u , cost;
    node(){};
    node(int dis,int u,int cost):dis(dis),u(u),cost(cost){};
    bool operator>(const node& a) const { 
        if(dis==a.dis)return cost > a.cost;
        return dis > a.dis; 
    }
};

int k,n,m;
vector<edge> e[MAXN];
int dis[110][10010],vis[110][10010];

void dijkstra(int s){
    priority_queue<node,vector<node>,greater<>>que;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            dis[i][j]=inf;
        }   
    }
    dis[s][0]=0;
    que.push({0,s,0});
    while(que.size()){
        auto [d,u,c]=que.top();
        que.pop();
        if(vis[u][c])continue;
        vis[u][c]=1;
        for(auto [v,w,t]:e[u]){
            if(c+t<=k&&dis[v][t+c]>dis[u][c]+w){
                dis[v][t+c]=dis[u][c]+w;
                if(!vis[v][t+c])
                que.push({dis[v][t+c],v,t+c});
            }
        }
    }
}
void solve()
{
    cin>>k>>n>>m;
    for(int i=1,s,d,l,t;i<=m;i++){
        cin>>s>>d>>l>>t;
        e[s].emplace_back(d,l,t);
    }
    dijkstra(1);
    int ans=inf;
    for(int i=0;i<=k;i++){
        ans=min(dis[n][i],ans);
    }
    if(ans==inf)cout<<"impossible";
    else cout<<ans;
}
//#define LOCAL
signed main(){
    ios
    //fre
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto start = std::chrono::high_resolution_clock::now();
    #endif
    
    int _=1;
    // cin>>_;
    while(_--)solve();
    
    #ifdef LOCAL
    auto end = std::chrono::high_resolution_clock::now();
    cout << "Execution time: "
         << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
         << " ms" << '\n';
    #endif
    return 0;
}

F 美丽序列

此题考虑线段树维护，合并两棵子树时：

左子树的贡献为：

a_{l1} a_{l1} * a_{l1 1} ... a_{l1} * ... a_{r1}

右子树的贡献为:

a_{l2} a_{l2} * a_{l2 1} ... a_{l2} * ... a_{r2}

合并左右子树后该区间的贡献为:

a_{l1} a_{l1} * a_{l1 1} ... a{l1} * ... * a_{r2}

考虑提取公因式：

(a_{l1} a_{l1} * a_{l1 1} ... a_{l1} * ... * a_{r1}) a_{l2} * (a_{l1} a_{l1} * a_{l1 1} ... a_{l1} * ... * a_{r1}) ... \\ (a_{l2} ... a_{l2} * ... * a_{r2}) * (a_{l1} a_{l1} * a_{l1 1} ... a_{l1} * ... * a_{r1})

我们发现，合并后该区间的贡献即为，左子树的贡献加上左子树最后一项的值乘上右子树的贡献

区间修改时，将该区间改为同一个数，该区间的贡献可以用等比数列求和公式求出，该区间的最后一项也可以用等比数列公式求出。

剩下的就是套路性的东西。

参考代码:

#include <bits/stdc++.h>

#define lson (rt << 1)
#define rson (rt << 1 | 1)

using i64 = long long;

int a[200005];
const i64 mod = 998244353;
struct node {
    i64 v, rmx;
    int lz;
}tr[200005 << 2];

i64 ksm(i64 a, i64 b) {
    i64 res = 1;
    while(b) {
        if (b & 1) {
            res = res * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }

    return res;
}

node mer(node x, node y) {
    if (x.v == 0 ) return y;
    node res = {0, 0, 0};
    res.v = x.rmx * y.v % mod + x.v;
    res.v %= mod;
    res.rmx = x.rmx * y.rmx % mod;
    return res;
}

void push_down(int rt, int l, int r) {
    if (tr[rt].lz) {
        int mid = l + r >> 1;
        int x = tr[rt].lz;
        tr[lson].lz = x;
        tr[rson].lz = x;

        tr[lson].v = (ksm(x, mid - l + 1) - 1) * x % mod * ksm(x - 1, mod - 2) % mod;
        tr[rson].v = (ksm(x, r - mid) - 1) * x % mod * ksm(x - 1, mod - 2) % mod;

        tr[lson].rmx = ksm(x, mid - l + 1);
        tr[rson].rmx = ksm(x, r - mid);
        
        tr[rt].lz = 0;
    }
}

void build(int rt, int l, int r) {
    if (l == r) {
        tr[rt].v = a[l];
        tr[rt].rmx = a[l]; 
        return;
    }

    int mid = l + r >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    tr[rt] = mer(tr[lson], tr[rson]);
}

void update(int rt, int l, int r, int L, int R, int x) {
    if (l >= L && r <= R) {
        tr[rt].lz = x;
        tr[rt].v = (ksm(x, r - l + 1) - 1) * x % mod * ksm(x - 1, mod - 2) % mod;
        tr[rt].rmx = ksm(x, (r - l + 1));
        return;
    }

    push_down(rt, l, r);

    int mid = l + r >> 1;
    if (mid >= L)
        update(lson, l, mid, L, R, x);
    if (mid < R) {
        update(rson, mid + 1, r, L, R, x);
    }
    tr[rt] = mer(tr[lson], tr[rson]);
}

node query(int rt, int l, int r, int L, int R) {
    if (l >= L && r <= R) {
        return tr[rt];
    }

    push_down(rt, l, r);
    node res = {0, 0, 0};

    int mid = l + r >> 1;
    if (mid >= L) {
        res = mer(res, query(lson, l, mid, L, R));
    }
    if (mid < R){
        res = mer(res, query(rson, mid + 1, r, L, R));
    }
    return res;
}

void solve() {
    int n, m;
    std::cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    build(1, 1, n);

    while (m--) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int l, r, x;
            std::cin >> l >> r >> x;
            update(1, 1, n, l, r, x);
        }
        else {
            int l, r;
            std::cin >> l >> r;
            std::cout << query(1, 1, n, l, r).v << '\n';
        }
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

G 正方形的个数

考虑枚举边与 x,y 轴平行的正方形, 对于每个边与 x,y 轴平行的正方形 X(边长为 n 个点) 来说, 其内部四个点都在 X 的边上, 且边为斜的的正方形个数为 $n-2$ 个.

#define int long long
const int M = 1e9 + 7;

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, ans = 0;
    cin >> n;

    for (int i = n; i >= 2; --i) {
        ans += (i - 1) * (n - i + 1) % M * (n - i + 1) % M;
        ans %= M;
    }

    cout << ans << endl;
}

H 红温lz

一个很明显的贪心结论，最优解k一定满足在和某一座山高减1处即 $k == h_{i} - 1$

参考代码:

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::priority_queue<std::pair<int, int>>q;

    std::vector<int> h(n), a(n);
    for (int i = 0; i < n; i++) std::cin >> h[i];
    for (int i = 0; i < n; i++) std::cin >> a[i];

    for (int i = 0; i < n; i++) {
        q.push({h[i], a[i]});
    }

    i64 ans = -1, sum = 0, now = 0, lst = 0,  pre = 0;
    for (int i = 0; i < n; i++) {
        i64 sum1 = 0;
        auto [h, a] = q.top();
        now = h - 1;
        sum += i * (lst - now) + 1;
        lst = now;
        pre += a;
        sum1 += pre - sum;
        ans = std::max(ans, sum1);
        q.pop();
    }

    std::cout << ans << '\n';
}
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t=1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}