浪在ACM12.07第八次训练赛

54 阅读 0 评论 36 点赞

我是靠谱客的博主虚幻微笑，最近开发中收集的这篇文章主要介绍浪在ACM12.07第八次训练赛，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

应该是ljp测试小巨巨们有没有掌握上次的两个题(怎么肥四？？?这好像是我讲的题？？难道我表达能力这么弱嘛QAQ(。・・)ノ)

前两个的题解再扔一遍https://blog.csdn.net/QLU_minoz/article/details/84639264，再不会就要打人辣(* ￣︿￣)超凶

重点说一下后两个题

C. Minimizing the String

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a string ss consisting of nn lowercase Latin letters.

You have to remove at most one (i.e. zero or one) character of this string in such a way that the string you obtain will be lexicographically smallest among all strings that can be obtained using this operation.

String s=s1s2…sns=s1s2…sn is lexicographically smaller than string t=t1t2…tmt=t1t2…tm if n<mn<m and s1=t1,s2=t2,…,sn=tns1=t1,s2=t2,…,sn=tn or there exists a number pp such that p≤min(n,m)p≤min(n,m) and s1=t1,s2=t2,…,sp−1=tp−1s1=t1,s2=t2,…,sp−1=tp−1 and sp<tpsp<tp.

For example, "aaa" is smaller than "aaaa", "abb" is smaller than "abc", "pqr" is smaller than "z".

Input

The first line of the input contains one integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the length of ss.

The second line of the input contains exactly nn lowercase Latin letters — the string ss.

Output

Print one string — the smallest possible lexicographically string that can be obtained by removing at most one character from the string ss.

别看题目这么长就是让你找一下最小字典序，类似于校赛的老虎机？八过！数字变成了字母，这一改变就比老虎机简单多惹

思路就是越靠前的字符字典序越小，总的字典序就会越小。所以从前面往后遍历找比后面字母字典序大的就ok惹，如果没有的话，就删除最后一个咯，因为子串的字典序比这个串的字典序小鸭ε=ε=ε=(~￣▽￣)~，我们就可以在最后面加上一个比字母小的字符比如'0'就可以一遍遍历过去不用特判惹

#include<bits/stdc++.h>
using namespace std;
int const maxn=200005;
int n;
char s[maxn];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
    }
    s[n]='0';//额外加小字符便于比较
    for(int i=0;i<n;i++)
    {
        if(s[i]>s[i+1])//寻找前一个比后一个字典序大的字符
        {
             s[i]='0';//找到了就标记一下
             break;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(s[i]!='0')//不输出相当于删除
            cout<<s[i];
    }

}

D. Divisor Subtraction

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an integer number nn. The following algorithm is applied to it:

if n=0n=0, then end algorithm;
find the smallest prime divisor dd of nn;
subtract dd from nn and go to step 11.

Determine the number of subtrations the algorithm will make.

Input

The only line contains a single integer nn (2≤n≤10102≤n≤1010).

Output

Print a single integer — the number of subtractions the algorithm will make.

这个题看着复杂，其实理解题意就特别简单辽。注意数据范围，我不会说我wa4是因为爆int 运行错误惹 QAQ

这么来想，一个数变成他减去他的最小质因子，看能减多少次。如果这个数是偶数的话，他的最小质因子肯定是2，减2还是偶数，所以就看他有多少个2就阔以辽。如果是奇数的话，他的最小质因子肯定是奇数，那奇数-奇数又变成偶数惹。不过这里要注意一点，其实样例也给我们提出来了，他可能本身就是个奇数，这里要处理一下。再用上次查找特定指数和优化的方式，优化一下遍历范围，就好了。

#include<bits/stdc++.h>
using namespace std;
long long n;
int main()
{
    scanf("%lld", &n);
    if(!(n&1))//偶数
    {
        printf("%lldn", n/2);
        return 0;
    }
    else//奇数
    {
        int Count=0,flag=n;//如果本身是质数
        for(long long i=2;i*i<=n;i++)//优化，如果不是质数，最小质因子肯定小于根n
        {
            if(n%i==0)
            {
                flag=i;//最小质数改变成i
                break;
            }
        }
        n-=flag;
        Count++;
        printf("%lldn", Count+n/2);
    }
}