https://codeforces.com/contest/1473

 

A

题意：一个数组，可以用两个不同的元素替换掉另外一个元素，不限次数。问，能否使得数组中所有元素都不大于 d 。

思路：显然，如果所有元素都不大于d，那就执行0次。成立。如果有元素大于d，那就得替换掉，显然选择最小的两个元素进行替换。所以如果最小的两个元素加起来大于d那就没戏了。反之有解。

#include <algorithm>
#include <iostream>
using namespace std;
 
const int N = 110;
 
int t, n, d, a[N];
 
int main() {
    cin >> t;
    while (t--) {
        cin >> n >> d;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a, a + n);
        cout << ((a[0] + a[1] <= d || a[n - 1] <= d) ? "YES" : "NO") << endl;
    }
 
    return 0;
}

View Code

 

 

B

题意：两个字符串，定义字符串的因子就是，字符串中重复出现的子串。如“abab” 的因子就是“ab”和“abab”，现在要 求两个字符串的lcm。 也就是说，s1,s2，都是lcm的因子。

思路：先判断两个字符串最小循环节是不是一样，( s+t == t+s ) , 再通过最小公倍数的求法，直接取出两个字符串的最小公倍数个数循环出结果

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
 
int gcd(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
 
string gcd_str(string s, string t) {
    if (s + t != t + s) return "";
    return s.substr(0, gcd(s.size(), t.size()));
}
 
int main() {
    int n;
    cin >> n;
    while (n--) {
        string s, t, gcd_st, res = "";
        cin >> s >> t;
        gcd_st = gcd_str(s, t);
        if (gcd_st == "") {
            puts("-1");
            continue;
        }
        int len_gcdst = gcd_st.size();
        int len_lcmst = (s.size() / gcd_st.size()) * (t.size() / gcd_st.size());
 
        for (int i = 0; i < len_lcmst; i++) {
            res += gcd_st;
        }
        cout << res << endl;
    }
 
    return 0;
}

View Code

 

 

C

题意：输入n(9)和k(6)，数组a是从1到k，k到2k-n的数组。b[i] = p[a[i]]，要求数组b的逆序对数量小于等于a，求p数组字典序最大，p是1到k的一个排列。
思路：打表发现，p数组是a序列第k个数开始到最后一个数，然后在这段数前面从1开始添加数，直到p数组的数字个数等于k为止。
比如a[] = {1,2,3,4,5,6,5,4,3} ——> p[] = {1,2,6,5,4,3};

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k;
        scanf("%d%d", &n, &k);
        int sum = k - (n - k);
        for (int i = 1; i < sum; i++) printf("%d ", i);
        for (int i = k; i >= sum; i--) printf("%d ", i);
        puts("");
    }
}

View Code

 

D

题意：x，初始为0，两种操作，’+’ 表示 x += 1，’-’ 表示 x -= 1。然后题目给出一系列操作。然后q个询问 l,r。表示删掉区间 [l-r]，之内的操作，剩下的操作，可以让x变成多少不同的值。

思路：首先考虑在没有删除的情况下，一系列操作过程中，能变成多少不同的值。x初始为0，随着+/-的变化，会来回反复横跳，那么两个关键点就是最大值和最小值，这说明从最大值到最小值之间的数字，都是在操作过程中出现。所以只需要考虑一个区间内的操作产生的最大最小值。

由于是讨论取值有多少种,假如说没有这个删除操作,那么我们只需要统计整个过程中x的最小值和最大值,也就是x可以取到的值域,就可以知道他有多少种取值了.接下来考虑怎么做维护.

由于最大值和最小值两个问题独立,只做一边最小值,另一边对称即可.如果删掉了[l,r]这段操作,那么新的这段过程中,最小值有两种来源:第一种是l−1这个操作以及他之前的操作可以让x得到的最小值,还有一种是从l−1这段刚好接到r+1这段之后取的的最小值.

考虑做一个前缀和s[i]表示x前次操作的前缀和.根据上面的分析还需要维护一个在ll次操作及其之前能取得到的最小值,记作pmn[i].那么前者就是其直接定义.现在来看第二种怎么拼接的,首先比较容易想到的是要跟前面一样倒过来求一个后缀的最小值smn[i],注意这里的后缀的最小值是对前缀和而言的,不是对原始数列而言的.这里的smn[i]表示在执行了j∈[i,n]次操作中s[j]能取得的最小值,那么拼接过来实际上也就是让整一段smn[r+1]之中去掉删去的这一段的影响,也就是smn[r+1]−d其中d=s[r]−s[l−1].两种情况直接统计就可以了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)    
#define forr(i,x,n)    for(int i = n;i >= x;--i)

const int N = 2e5+7;
char s[N];
int pmn[N],pmx[N],smn[N],smx[N];
int a[N],pre[N],suf[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n,m;scanf("%d%d",&n,&m);
        scanf("%s",s + 1);
        
        forn(i,1,n)
        {
            a[i] = a[i - 1];
            if(s[i] == '+')    ++a[i];
            else             --a[i];
            pmn[i] = min(pmn[i - 1],a[i]);
            pmx[i] = max(pmx[i - 1],a[i]);
        }
        smn[n + 1] = 1e9,smx[n + 1] = -1e9;
        forr(i,1,n)
        {
            smn[i] = min(smn[i + 1],a[i]);
            smx[i] = max(smx[i + 1],a[i]);
        }
        // + + + + + + + + + - - - - - - - -        
        // 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1   0 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 0 -1 -2 -3
    //pmn  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -2 -3
    //pmx  1 2 3 4 5 6 7 8 9 9 9 9 9 9 9 9 9   0 1 2 3 4 5 6 7 8 9 9 9 9 9 9 9 9 9 9  9  9  9
    //smn  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  -3-3-3-3-3-3-3-3-3-3-3-3-3-3-3-3-3-3-3 -3 -3 -3
    //smx  9 9 9 9 9 9 9 9 9 8 7 6 5 4 3 2 1   9 9 9 9 9 9 9 9 9 9 8 7 6 5 4 3 2 1 0 -1 -2 -3
        while(m--)
        {
            int l,r;scanf("%d%d",&l,&r);
            int d = a[r] - a[l - 1];
            int dw = min({pmn[l - 1],smn[r + 1] - d});//zuixiao 
            int up = max({pmx[l - 1],smx[r + 1] - d});//zuida
            printf("%d\n",up - dw + 1);
        }
    }
    return 0;
}

View Code

 

E

题目大意:给定一个n点m边有权无向图,图中没有自环和重边.定义一条路径的权是路径上所有的边权之和减去所有边权最大值并加上所有边权的最小值.对每个点i∈[2,n]求出从1到i的路径权最小值.

数据范围:

2≤n≤2∗105

1≤m≤2∗105

1≤wi≤109

思路

这个题还是比较显然是最短路的拓展的,需要考虑最大值和最小值,对于这种有附加状态的最短路直接把附加状态和当前到的点放在一起就可以了,这里考虑怎么附加.首先肯定不能直接把最大值和最小值直接和distdist放在一起,范围太大了,即使离散化了也无法接受.考虑转换权值的统计:所有边权之和减掉最大值加上最小值等价于删除一条边并使一条边代价乘2,考虑这种操作得到的结果是否和原来的权值对应:因为求的是最短路,那么删除最小值,加上最小值的两倍一定是最优的,所以这样转换操作之后得到的最短路的结果等价于原来题目的减去最大值和加上最小值的操作.

把dist拓展成dist[u][j][k]表示从起点走到u时,j=1表示已经删除了一条边,k=1表示已经让一条边代价翻倍时的最短路长度.由于所有边权一定都是≥0的直接从起点跑dijkstra就可以了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)    
#define int ll
const int N = 2e5+7,M = 2 * N,INF = 1e9;
int edge[M],succ[M],cost[M],ver[N],idx;
int n,m;
ll dist[N][2][2];
bool st[N][2][2];
struct Node
{
    int u;
    ll dist;
    int j,k;
    bool operator>(const Node& _o)    const
    {
        return dist > _o.dist;
    }
};

void add(int u,int v,int w)
{
    edge[idx] = v;
    cost[idx] = w;
    succ[idx] = ver[u];
    ver[u] = idx++;
}

void dijkstra()
{
    forn(i,1,n)    forn(j,0,1)    forn(k,0,1)    dist[i][j][k] = 1e18;
    priority_queue<Node,vector<Node>,greater<Node>> pq;pq.push({1,0,0,0});dist[1][0][0] = 0;
    
    while(!pq.empty())
    {
        auto f = pq.top();pq.pop();
        ll d = f.dist;int u = f.u,f1 = f.j,f2 = f.k;
        if(st[u][f1][f2])    continue;
        st[u][f1][f2] = 1;
        for(int i = ver[u];~i;i = succ[i])
        {
            int v = edge[i];
            if(dist[v][f1][f2] > d + cost[i])
            {
                dist[v][f1][f2] = d + cost[i];
                pq.push({v,dist[v][f1][f2],f1,f2});
            }
            if(f1 == 0 && dist[v][1][f2] > d)
            {
                dist[v][1][f2] = d;
                pq.push({v,dist[v][1][f2],1,f2});
            }
            if(f2 == 0 && dist[v][f1][1] > d + 2 * cost[i])
            {
                dist[v][f1][1] = d + 2 * cost[i];
                pq.push({v,dist[v][f1][1],f1,1});
            }
            if(f1 == 0 && f2 == 0 && dist[v][1][1] > d + cost[i])
            {
                dist[v][1][1] = d + cost[i];
                pq.push({v,dist[v][1][1],1,1});
            }
        }
    }
}


signed main()
{
    memset(ver,-1,sizeof ver);
    scanf("%lld%lld",&n,&m);
    forn(i,1,m)
    {
        int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    
    dijkstra();
    
    forn(i,2,n)    printf("%lld ",dist[i][1][1]);
    return 0;
}

View Code

 

F

https://www.cnblogs.com/HotPants/p/14283612.html

看不懂了~