“科大讯飞杯”第18届上海大学程序设计联赛春季赛暨高校网络友谊赛 A-L 解题报告

A 组队比赛

题目类型:思维

题目链接:

A-组队比赛

题目大意:

给你四个数组,两两一组,每组实力值为队内实力值之和,求解两组差值最小

解题思路:

四个数组排序,最大与最小,第二与倒二,绝对值下差值即可

代码:

int a[4];
int main(){
    cin >> a[0] >> a[1] >> a[2] >> a[3];
    sort(a, a+4);
    cout << abs(a[0] + a[3] - a[1] - a[2]) << '\n';
}

B 每日一报

题目类型:模拟、排序

题目链接:

B-每日一报

题目大意:

给你一份n个学生的数据,里面包含学生的测温时间、学号、体温三个信息,现在要求你取出大于38.0的学生信息,并按照如下要求进行排序

链接:https://ac.nowcoder.com/acm/contest/5278/B
来源:牛客网
报送日期不一致的,则日期较近的在上,日期较久远的在下;
报送日期一致体温不一致的,则体温高的在上,体温低的在下;
报送日期和体温都一致的,则学号小的在上,学号大的在下。

解题思路:

通过结构体排序实现

代码:

struct sit{
    string day, num; DB tem;
} a[101];
bool cmp (sit fir, sit sed){
    if (fir.day != sed.day) return fir.day > sed.day;
    else if (fir.tem != sed.tem) return fir.tem > sed.tem;
    else {
        return fir.num < sed.num;
    }
}
int main(){
    int n, k = 0; cin >> n;
    REP(i, n){
        string rday, rnum; DB rtem;
        cin >> rday >> rnum >> rtem;
        if (rtem >= 38.0) a[k].day = rday, a[k].num = rnum, a[k].tem = rtem, k++;
    }
    OT(k);
    sort(a, a+k, cmp);
    REP(i, k) {
        cout << a[i].day << " " << a[i].num << " "; printf("%.1f\n", a[i].tem);
    }
}

C 最长非公共子序列

题目类型:思维

题目链接:

C-最长非公共子序列

题目大意:

给你两段字符串,现在要求你求解,最长不相同子序列的长度

解题思路:

其实很简单,原比最长公共子序列容易的多,两个字符串完全相同的情况下是不可能有不相同子序列的,而一但两个字符串不同直接输出较长那个字符串的就可以了,简单的思维题

代码:

int main(){
string s1, s2; cin >> s1 >> s2;
if (s1 == s2) cout << "-1" << '\n';
else cout << max(SZ(s1), SZ(s2)) << '\n';
}

D 组队比赛

题目类型:思维

题目链接:

D-最大字符集

题目大意:

给你一个n,要求你求解出最多01字符串,这些字符串要求相互不是子串,且任意两两长度不同

解题思路:

实际上当你写几个01字符串你会发现几个要点

  1. 1或0会是所有长度大于等于的字符串的子串(这一点是告诉你要特判n=2的情况)
  2. 两个1中间不断加0比不可能是上一串的子串

针对第二个我写几个,就很好理解了,

11
101
1001
10001
100001
你会发现恰好满足长度不一致,且不互为子串的条件(00也一样),所以只需要特判n=1和n=2的情况就可以了

代码:

int main(){
    int n; cin >> n; 
    if (n == 1){ cout << 1 << '\n' << 1 << '\n';}
    else if (n == 2) cout << "2\n" << 0 << '\n' << "11" << '\n'; 
    else { cout << n - 1 << '\n';
        REP(i, n - 1){
            cout << "1"; REP(j, i){cout << "0";} cout << 1 << '\n';
        }
    }
}

E 组队比赛

题目类型:思维

题目大意:

给你一个长度为n的数组,每个位置的值表示美味度(即\(a[i]\)),你可以从头或者从尾食用,一秒只能食用一个,并且未被食用的部分会美味度-1,要求你求解最大的总美味度

解题思路:

这题你可能会思考,到底是从头吃呢还是从尾吃呢,其实是没差别的,因为

他用数字标识了每个部分的美味度(可能是负的)

美味度可能是负值,你要减去的数量就一定会

\((n - 1) * n / 2\)

可以边加边减,也可以全部加完再减

代码:

有人可能会是第一种方法,却wa了,n必须要是是LL,为什么n要是LL呢?
明明题目给的数据没有溢出啊,是因为在计算\((n - 1) * n / 2\)的时候溢出的,这个可能导致你的wa(还好我用的是第二个方法QAQ)

int main(){
    LL n; cin >> n;
    LL ans = 0;
    REP(i, n){
        LL x; scanf("%lld",&x);
        ans += x;
    }
    ans -= (n - 1) * n / 2;
        OT(ans);
}
int main(){
    int n; cin >> n;
    LL ans = 0;
    REP(i, n){
        int x; scanf("%d",&x);
        ans += x - i;
    }
        OT(ans);
}

F 组队比赛

题目链接:

F-组队比赛

题目类型:模拟

题目大意:

母亲节和父亲节你需要送礼,对于每一个日期,输出下一个需要送礼的日子(下一个需要送礼的日子可能是母亲节也可能是父亲节)

解题思路:

依照模拟,需要判断的实际上就是下一个节日是什么,
母亲节在8到14之间变动

if(a[i] < 8)   a[i] += 7;

,父亲节在15到21之间变动,

if(b[i] < 15)  b[i] += 7;

代码:

const int maxn = 200;
int a[maxn], b[maxn];
int main(){
    int n = 0, p;
    a[0] = 14;
    b[0] = 18;
    FOR_1(i, 1, 103)
    {
        a[i] = a[i-1]-1;
        b[i] = b[i-1]-1;
        if(i % 4 == 0 && i != 100)
        {   
            a[i]--; 
            b[i]--; 
        }//闰年
        if(a[i] < 8)   a[i] += 7;
        if(b[i] < 15)  b[i] += 7;
    }
    int _; for(scanf("%d", &_); _; _--){
        int y, m, d;scanf("%d%d%d",&y,&m,&d);   n = y - 2000; //易知是从2000年开始
        if(m > 6 || m == 6 && d >= b[n])
            printf("Mother's Day: May %dth, %d\n",a[n+1], y+1);
        else if(m < 5 || m == 5 && d < a[n])
            printf("Mother's Day: May %dth, %d\n",a[n], y);
        else if(b[n]!=21)
            printf("Father's Day: June %dth, %d\n",b[n], y);
        else    printf("Father's Day: June 21st, %d\n", y);
    }
}

G 血压游戏

题目链接

G-血压游戏

题目类型:树

题目大意:

官方题意

Compute 有一棵 n 个点,编号分别为 1∼n 的树,其中 s 号点为根。
Compute 在树上养了很多松鼠,在第 i 个点上住了 ai 个松鼠。
因为某些缘故,它们开始同时向根节点移动,但它们相当不安分,如果在同一个节点上,它们就会打起来,简单地来说以下事件会依序发生:
如果一个节点上有 2 只或 2 只以上的松鼠,他们会打架,然后这个节点上松鼠的数量会减少 1;
根节点的所有松鼠移动到地面,位于地面上的松鼠不会再打架;
所有松鼠同时朝它们的父节点移动。
所有事件各自都在一瞬间完成,直至树上没有松鼠。
现在 Compute 想知道最终有多少只松鼠到达了地面。

乱搞题意

给你一个树,每个节点上都有\(a[i]\)个松鼠,所有位置上的松鼠都是向父节点进行移动的,而根节点上的松鼠是向地面上移动,就是从根节点移动出去
每次的操作时这样的

  1. 如果一个节点上有 2 只或 2 只以上的松鼠,他们会打架,然后这个节点上松鼠的数量会减少 1;
  2. 根节点的所有松鼠移动到地面,位于地面上的松鼠不会再打架;
  3. 所有松鼠同时朝它们的父节点移动。

题目问的是最后到地面上的松鼠有多少只

解题思路:

结论1

由于每一步的松鼠都是向父节点移动的,只有一个节点上有2只或者两只以上的松鼠才会打架,那么可以确定 只有同一层上的松鼠才会相互打架

  1. 因为是同一时间进行向父节点进行移动的

思考1

由于是子节点向父节点进行移动所以可以考虑子树合并的思想,(可以思考是不是树上启发式合并的方法)

思考2

由于是不断的向上移动,也就是每个节点需要不断的查询,那么可能会面临较多次数的查询次数, 可以思考是不是需要使用虚树这个数据结构呢?

虚树中包含了所有的关键点,也包含了所有关键点两两之间的 LCA(lowest common ancestor, 最近公共祖先)(LCA 的数量不超过关键点的个数,稍后有证明),这就保证了虚树不会丧失原有的树形结构,同时尽可能地压缩了树的大小。同时虚树中 uu 到 vv 的边权定义为原树中 uu 到 vv 的最短路径
关于虚树虚树学习笔记

dp[x]=∑t∈sonx ,dp[t]>0max{1,dp[t]−(deep[t]−deep[x])}

 for(auto k : ma[rt])
        if(k.second)
            ans += max(1ll, k.second-tag[rt]);

总结

方法1 .利用DFS序合并区间虚树的线段树 && 启发式合并的思想
方法2. 虚树构建一下,再进行dp,根据子节点情况去计算父节点情况(将子节点合并到父节点上),满足通过计算有限集统计总和情况

树上合并式启发

void merge(int x, int y) {
  int xx = find(x), yy = find(y);
  if (size[xx] < size[yy]) swap(xx, yy);
  fa[yy] = xx;
  size[xx] += size[yy];
}

虚树
我们将两个大小不一样的集合,我们将小的集合合并到大的集合中,而不是将大的集合合并到小的集合中。

为什么呢?这个集合的大小可以认为是集合的高度(在正常情况下),而我们将集合高度小的并到高度大的显然有助于我们找到父亲
让高度小的树成为高度较大的树的子树,这个优化可以称为启发式合并算法。

代码:

const int maxn = 200100;
 
int n, rt;
LL ans;
int a[maxn];
vector<int> G[maxn];
 
int fa[maxn], dep[maxn];
LL tag[maxn];
 
map<int, long long> ma[maxn];
 
void inse(int u, int d, long long val)
{
    if(!ma[u].count(d))
        ma[u][d] = val+tag[u];
    else
        ma[u][d] = max(ma[u][d], tag[u]+1) + val;
}
 
void merg(int u, int v)
{
    if(ma[v].size() > ma[u].size())
    {
        swap(ma[u],ma[v]);
        swap(tag[u],tag[v]);
    }
    for(auto i : ma[v])
        if(i.second)
            inse(u, i.first, max(i.second-tag[v], 1ll));
}//将小的子树合并到大的父节点中
void dfs(int u)
{
 
    dep[u] = dep[fa[u]] + 1;
    for(int v : G[u])
    {
        if(v == fa[u]) continue;
        fa[v] = u;
        dfs(v);
        merg(u, v);
    }
    if(a[u])
        inse(u, dep[u], a[u]);
    tag[u]++;
} 
 
int main()
{
    scanf("%d%d", &n, &rt);//点的数量和根的编号
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for(int i = 2; i <= n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(rt);
    for(auto k : ma[rt])
        if(k.second)
            ans += max(1ll, k.second-tag[rt]);
    printf("%lld\n", ans);
}

H 纸牌游戏

题目链接:

H-纸牌游戏

题目类型:数学

题目大意:

给你一个字符串s 要求你拼出一个长度为 k 的同时能被 3 整除的最大非负整数,并且不能有前导0

解题思路:

什么样的数能被3整除?

该数字的各个位置上的数相加之和能被3整除,那么该数也一定能被3整除

注意

一开始我求简便,是这么做,因为要最大,所以我直接排序,取较大的k个数字,然后判断是否能被3整除,如果不行我选一位去枚举和后面一位交换直到成立,这么做是不对的,因为当需要出现交换两个的时候就会出错,这里给出一下样例,有兴趣的可以跑一下

输入
998244151 3
输出
984

正文

1.我们因为每位字符纯粹是我们自己决定的,没有什么其他的要求,所以我们完全可以统计0-9数字出现的次数去进行组合
2.取余3为1的数字和取余3位2的数字组合之和一定能被3整除,例如2和1
3.我们在组合区间枚举出符合条件最大的就可以

代码:

int cntmod[3]; // 被3取余后只会有3种情况 0, 1, 2,这里对三种情况进行一下计数
int cnt[10];
bool judge(int x, int m){
    if (!m) return !x;
    int a = cntmod[0], b = cntmod[1],c = cntmod[2];
    int l0 = max(0, m - b - c), r0 = min(a, m);
    //一个除3余数为1的数和一个除3余2的数匹配就是一个能被3整除的数,例如1和2, 那么我们就枚举这些组合判断是否能被整除
    for(int i = l0; i <= r0; i++){
        int t = ((2 * (m - i) - x) % 3 + 3 ) % 3;
        int l1 = max(0, m - i - c), r1 = min(b, m - i);
        while(l1 % 3 != t) l1++;
        if(l1 <= r1) return true;
    }
    return false;
}

void init(){
    //初始化
    memset(cntmod, 0, sizeof cntmod);
    memset(cnt, 0, sizeof cnt);
}
int main(){
    int _;
    for(scanf("%d", &_); _; _--){
        init();
        string s; int k;
        cin >> s >> k;
        int len = SZ(s);
        FOR(i, 0, SZ(s)){
            cnt[s[i] - '0']++; cntmod[(s[i] - '0') % 3]++;
        }
        //统计
        int n;
        for(int i = 9, j = n = 0; i >= 0; i--){
            //枚举各个数出现次数之前已经统计过了,现在只是运用
            while(cnt[i] > 0 && n < k){
                int t = (i + j) % 3;
                cnt[i]--, cntmod[i % 3] --;//如果这数字字i使用了,就减去
                if (!judge((3 - t) % 3, k - n - 1)){
                    cnt[i]++, cntmod[i % 3]++;
                    break;//如果不能被整除那么就回溯,不使用这个i
                }
                s[++n] = '0' + i;j = t;
            }
        }
        //s[n + 1] = '\0';
        if(n < k || (s[1] == '0' && n > 1)) OT("-1");//出现前导0的情况
        else {
            FOR_1(i, 1, n){
                cout << s[i];
            }
            OT("");
        }
    }
}

I 组队比赛

题目类型:

题目大意:

解题思路:

代码:

J 组队比赛

题目类型:

题目大意:

解题思路:

代码:

K 组队比赛

题目类型:

题目大意:

解题思路:

代码:

L 组队比赛

题目类型:

题目大意:

解题思路:

代码:

上一篇:MSCE C++官网一步步学习搬运1


下一篇:线段树BIT操作总结