题目来源：清北学堂

天天寄快递

express.in/.out/.cpp

【问题描述】

天天暑假时帮别⼈寄送快递，经历了⼀个暑假，天天积累了不少数据，

想对快递公司进⾏⼀下评分，得到快递公司的质量⽔平。

总共有 n 家快递公司，编号为 1..n。现在天天有 m 天的寄送快递数据，

其中第 i 天使⽤第 e i 家快递公司，快递在路上花了 t i 天时间。⼀开始每个

快递公司的评分都为 0，对于⼀家快递公司，如果⼀个包裹花了 t i 天寄到，

那么对这家快递公司的评分贡献为 2−t i ， （如果花的时间超过两天得分就会

变成负的啦） 。

然⽽事情没有这么简单，如果某⼀天的数据丢掉了，天天为了公平起见

就忽略掉这天的数据。于是快递公司联盟决定雇佣⼀个⼩偷，⼩偷可以偷⾛

最多 s 天的数据，使得每个公司的信⽤得分⾄少增加 k，且所有快递公司的

信⽤总和尽量⼤。

若如果被偷以后，⽆法让每个公司的信⽤得分都⾄少增加 k，输出

−23333333，否则请你输出被偷后, 所有快递公司的信⽤得分的和最多增

加多少。

【输入格式】

第⼀⾏四个整数 n,m,s,k，其中 1 ≤ n,m ≤ 100,000,0 ≤ s ≤ m,0 ≤

k ≤ 10 9 。

接下来 m ⾏，每⾏两个整数。接下来的第 i ⾏为 e i ,t i ，其中 1 ≤ e i ≤

n,0 ≤ t i ≤ 10 9 。

【输出格式】

⼀个整数，为题⽬要求的答案。

2

【样例输入】

2 5 4 22

1 1

1 40

2 25

2 30

2 0

【样例输出】

89

【样例解释】

⼩偷可以偷 4 天的数据，但是⼩偷实际上只偷了第 2,3,4 天的数据，1

号公司获得了 38 分的提升，2 号公司获得了 23 + 28 分的提升，都满⾜了

最⼩提升 22 分的要求。

【数据规模和约定】

对于 30% 的数据，1 ≤ n,m ≤ 20。

对于 100% 的数据，1 ≤ n,m ≤ 200,000,。

题解：贪心

代码：

考试30分....就是正解呀....靠 我知道了数组开小了，应该200005 嘤嘤嘤..改了就A 了...

#include
     
      #include
      
       #include
       
        using namespace std;#define maxn 100005int n,m,s,k,tot;int v[maxn];long long ans;inline int read(){    char ch=getchar();int x=0,f=1;    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';    return x*f;}struct WW{    int id,ad,has;}w[maxn];bool cmp(WW a,WW b){    return a.ad>b.ad;}bool check(){    for(int i=1;i<=n;i++)if(v[i]
        
         s){        printf("-23333333\n");        fclose(stdin);        fclose(stdout);        return 0;    }    sort(w+1,w+m+1,cmp);    if(tot
        
       
      
     

正解：贪心 

局部贪心：为了使每个公司都增加K,每次选可增加次数最多的，一旦增加到了K，就停止。

全局贪心：为了使总和最多，如果还能选每次在剩下选最大的

如果偷了s天仍没有使每个公司增加K,无解

代码：

唉...可能是考试使时间不多了敲得很慌张...按原来思路敲一遍就A了....

清北的题真不错.....

 

#include
     
      #include
      
       #include
       
        #include
        
         #define maxn 200005using namespace std;int n,m,s,k,day;int v[maxn];long long ans;struct WW{    int id,ad,has;}w[maxn];inline int read(){    char ch=getchar();int x=0,f=1;    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';    return x*f;}bool cmp(WW a,WW b){    return a.ad>b.ad;}bool check(){    for(int i=1;i<=n;i++)if(v[i]
        
       
      
     

 

 

 

 

天天和不可描述

unknown.in/.out/.cpp

【问题描述】

天天和 () 是好朋友，然⽽总是唱反调。对于⼀个有 () 的字符串，天天

总是会把 () 内的所有东西都倒过来读。

⽐如对于字符串 abc(def) ，天天看到的就是 abcfed 。

括号⾥⾯可能是空的， 也有可能套有多个括号， ⽐如说 abc(hello)(world)lcy()x(owq(zrt))

，天天看到的就是 abcollehdlrowlcyxzrtqwo 。

因为 (owq(zrt)) ⾸先变成了 (trz)qwo ，接下来变成了 zrtqwo ，zrt 被

反转了两次，所以天天看到的还是 zrt。

现在给你⼀个字符串，问你天天看到的是什么样⼦的？

【输入格式】

⼀⾏⼀个字符串，表⽰原始的字符串。保证字符串内只有⼩写字母和 (

以及) 组成。保证括号总是配对的。

【输出格式】

⼀⾏⼀个字符串，表⽰天天看到的字符串。

【样例输入 1】

abc(hello)(world)lcy()x(owq(zrt))

【样例输出 1】

abcollehdlrowlcyxzrtqwo

【样例输入 2】

(y(g(el)da)nis)

4

【样例输出 2】

singleday

【样例输入 3】

mian()

【样例输出 3】

mian

【数据规模和约定】

对于 10% 的数据，保证只出现⼀对括号，字符串长度⼩于 100,000。

对于另外 30% 的数据，保证字符串长度⼩于 100。

对于另外 40% 的数据，保证字符串长度⼩于 100,000。

对于剩余的 20% 的数据，保证字符串长度⼩于 500,000。

题解：

40分比赛代码...辣鸡...    咦？我去评测怎么80分.....T了2个点

统计每个括号的左右位置，stl里的函数进行从右到左翻转，从右到左是为了避免括号套括号混乱的情况

不过看这个得分好像没什么卵用。

//35分钟finish  reverse 只能对字符数组操作 #include
     
      #include
      
       #include
       
        #include
        
         #define maxn 500005using namespace std;int js,top;int vec[maxn];char s[maxn];struct WW{    int l,r;}w[maxn];bool cmp(WW a,WW b){    return a.l>b.l;}int main(){    freopen("unknown.in","r",stdin);    freopen("unknown.out","w",stdout);    cin>>s;    int len=strlen(s);    for(int i=0;i
         
          ='a'&&s[i]<='z')printf("%c",s[i]);    fclose(stdin);    fclose(stdout);    return 0;}
         
        
       
      
     

罪犯分组

prison.in/.out/.cpp

【问题描述】

B 城有1座监狱，1共关押着 N 名罪犯，编号分别为 1-N。

他们的关系十分不和谐。很多罪犯之间甚至积怨已久，如果客观条件具

备则随时可能爆发冲突。

在详细考察了 N 名罪犯间的⽭盾关系后，警察局长发现罪犯之间的⽭

盾关系可以⽤⼀个 N 个点 M 条边的⽆向图来表⽰：如果 x 到 y 有⼀条边，

表⽰罪犯 x 和罪犯 y 有⽭盾。

现在警察局长要把这些罪犯分成⼀些⼩组，每名罪犯属于且仅属于⼀个

⼩组。

为了开展活动顺利，要求每个⼩组内最多有 K 对罪犯有⽭盾，同时为

了管理⽅便，警察局长希望最小化分成的⼩组数量。

那么，应如何分配罪犯，才能使分成的⼩组数量最少？这个最⼩值是多

少？

【输入格式】

第3 个整数，N,M,K，意义见上述。

接下来 M 行，每行两个数字 x,y。表示x 和 y 之间有⽭盾。

【输出格式】

输出一行一个个值，表示最少的分组数量。

【样例输入】

3 3 1

1 2

2 3

1 3

6

【样例输出】

2

【数据规模和约定】

对于每个测试点，N 分别等于 2,4,6,8,10,12,14,15,16,16。

0 ≤ M,K ≤

N(N−1)

2

保证是1个无自环、无重边的无向图。

题解：

莫名其妙乱搞60分...受宠若惊...

乱合并..能一个房间就一个房间...顺便记录每个房间有多少个仇家。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;vector
          
           vec[22];int n,m,k,ans;int fa[22],d[22][22],tmp[22],v[22];int f(int x){ return fa[x]==x?x:fa[x]=f(fa[x]);}void change(int fx,int fy){ for(int i=0;i