T1 陪审团

【题目描述】

陪审团制度历来是司法研究中的一个热议话题，由于陪审团的成员组成会对案件最终的结果产生巨大的影响，诉讼双方往往围绕陪审团由哪些人组成这一议题激烈争夺。小 W提出了一个甲乙双方互相制衡的陪审团成员挑选方法：假设共有 n 名候选陪审团成员，则由甲先提名 s 位候选人，再由乙在甲提名的 s 位候选人中选出t名，作为最终的陪审团成员。显然这里应当有 n≥s≥t 。假设候选人k对甲、乙的有利程度都可以用一个二元组( xk ，yk )来表示，x.越大说明候选人 k 对甲越有利， yk 越大则对乙越有利。在此前提下，双方的目标都变得明确：甲要最大化最终陪审团 t 人的 x 之和，最小化 y之和，乙则反之。

现在甲方决定聘请你为律师，并且事先得知了乙方律师的策略：乙方律师会在你提名的 s名候选人中选出 t 名使得这 t 人的 y 值之和最大，再保证 y 值之和最大的前提下使得 x值之和尽量小（在对乙方最有利的前提下对甲方最不利）。

现在你应当慎重地提名 s 位候选人使得最终由乙方律师确定的 t 人 x 值和最大，若有多种方案，则应再使被乙方排除掉的 t-s 人的 y 值和尽量大，在此基础上最大化 s 人的 x值之和。 你的当事人并不关心你提名的具体是哪些人，只要你告诉他你提名的s人的x值之和与y值之和。

【输入格式】

第一行包含三个整数n,s,t。

接下来nn行，每行两个整数分别表示xk，yk。

【输出格式】

共一行两个整数，分别为x值之和与y值之和。

【数据规模】

对于30%的测试数据n≤20

对于50%的测试数据n≤100

对于100%的测试数据n≤100000，x，y≤1000000

解析

因为乙会从s个中选出t个对自己有利的，所以剩下s-t个就是不选的，所以n个中一定至少有s-t个未被选中，这就是y最小的s-t个。

所以我们先按y的大小排序一遍，最后的s-t个假设我们先选了，乙就没有选择的余地了。

然后我们按x的大小排序一遍，这样我们可以保证自己得到的结果是最大的。

但到了这里还有一个漏洞，那就是s-t的要尽可能大（多个方案下）。因此我们将第一遍的t个选择标记，在按y的从大到小排序若y值相同，则x值小的在后面。这样从后往前先找到自己的第一个标记处，往后重新选择s-t个，这s-t个肯定是y比前面的小，但是最大的，且s的x之和是最大的。

Code

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;long long n,s,t,sumx,sumy;struct person{    int x,y;    bool cho;}per[105000];bool cmp1(person a,person b){    if(a.y==b.y) return a.x>b.x;    return a.y
          
           b.y;    return a.x>b.x;}bool cmp3(person a,person b){    if(a.y!=b.y) return a.y>b.y;    if(a.x!=b.x) return a.x>b.x;    return ((int)(a.cho)-(int)(b.cho)>0);}int read(){    char ch;    bool flag=false;    int num=0;    ch=getchar();    while(ch>'9'||ch<'0')    {        if (ch=='-') flag=true;        ch=getchar();    }    while(ch>='0'&&ch<='9')    {        num=num*10+(ch-'0');        ch=getchar();    }    if (flag==true) num*=-1;    return num;}int main(){    n=read(),s=read(),t=read();    for(int i=1;i<=n;i++)    {        per[i].x=read();        per[i].y=read();    }    sort(per+1,per+n+1,cmp3);    sort(per+1,per+1+n-s+t,cmp2);    for(int i=1;i<=t;i++) per[i].cho=1;    sort(per+1,per+n+1,cmp3);    int first;    for(int i=n;i>=1;i--)        if(per[i].cho)        {            first=i;            break;        }    int i;    for(i=t+1,first++;i<=s;i++,first++) per[first].cho=1;    for(int i=1;i<=n;i++)        if(per[i].cho)        {            sumx+=per[i].x;            sumy+=per[i].y;        }    cout<
           
            <
           
          
         
        
       
      

 

 

 

 

 

 

T2 shine

【题目描述】

今天是NOIP初赛，Capo坐在考场上看着手中的初赛试卷，非常无聊，早已被钦点进入复赛的她在卷子上做了奇怪的事。 卷子可以看成一张n×m的方格纸，Capo手中有一支笔头截面是x×y矩形的笔，她在试卷上画下了一道痕迹，痕迹是由笔在纸面上做平行网格的运动画出的，笔不可以旋转，刚开始笔头截面的边平行与网格，每次移动，笔头只会向下或者向右移动一格。 阅卷老师Octavia看到了这张卷子，他对Capo的笔十分好奇，于是他想从笔迹中猜出笔头截面大小，请你告诉他x×y的最小值。

【输入格式】

第一行两个整数n,m表示卷子大小。 下面n行，每行m个字符，X表示有笔迹，.表示没有。

【输出格式】

一行一个整数，表示最小的x×y，无解输出-1。

【数据规模】

Subtask 1(10’):n,m≤10

Subtask 2(30’):n,m≤100

Subtask 3(10’):n=1,m≤1000

Subtask 4(20’):n=2,m≤1000

Subtask 5(30’):n,m≤1000

解析

现在左上方找到起点，再从起点向右方和下方延伸，

设最大延伸长度为x₀,y₀,显然x=x₀和y=y₀中必定有一个满足，设其中一个满足，再枚举另一个即可。

Code

#include
      
       #include
       
        using namespace std;#define sum(x1,y1,x2,y2) (s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1])int n,m;char c[1005][1005];int s[1005][1005];int ans=1000000000;int dfs(int x,int y,int wx,int wy){    if(sum(x,y+1,x+wx-1,y+wy)==wx*wy)return wx+dfs(x,y+1,wx,wy);    if(sum(x+1,y,x+wx,y+wy-1)==wx*wy)return wy+dfs(x+1,y,wx,wy);    return 0;}int main(){    freopen("shine.in","r",stdin);    freopen("shine.out","w",stdout);    scanf("%d%d\n",&n,&m);    int flag=0,px,py;    for(int i=1;i<=n;i++)        gets(c[i]+1);    for(int i=1;i<=n+1;i++)        for(int j=1;j<=m+1;j++)        {            if(c[i][j]=='X')            {                if(!flag){flag=1;px=i;py=j;}                s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+1;            }            else s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];        }    int tmp,wx,wy;    for(tmp=px;c[tmp][py]=='X';tmp++);    wx=tmp-px;    for(int i=py;c[px][i]=='X';i++)        if(sum(px,py,px+wx-1,i)==wx*(i-py+1)&&dfs(px,py,wx,i-py+1)+wx*(i-py+1)==s[n][m])            ans=min(ans,wx*(i-py+1));    for(tmp=py;c[px][tmp]=='X';tmp++);    wy=tmp-py;    for(int i=px;c[i][py]=='X';i++)        if(sum(px,py,i,py+wy-1)==(i-px+1)*wy&&dfs(px,py,i-px+1,wy)+(i-px+1)*wy==s[n][m])            ans=min(ans,(i-px+1)*wy);    if(ans<=n*m) cout<
       
      

 

 

 

 

 

 

T3 小P的世界

【题目描述】

小P的世界是一棵N（N<=1000）个节点的有根树（根为1），树上的每条边上都会有一个泡泡怪，小P从根节点开始移动（可以往回走），每经过一条边，小P都会打败边上的泡泡怪同时得到相应的泡泡气（每只泡泡怪只能被打败一次），已知 小P经过一条边需要花费 1 天时间，小P想知道自己晋级泡泡帝（泡泡气大于等于 K）至少需要的天数（如果 小P永远达不到泡泡帝，输出“QAQ”（不带引号））

【输入格式】

第一行两个用空格隔开的正整数 N，K。（1<=N<=1000，1<=K<=1000）

接下来 N - 1行每行三个用空格隔开的正整数 a，b，c，表示树上 a 与 b 之间连了一条边，打败边上的泡泡怪获得 c 点泡泡气（1<=a,b<=N，1<=c<=K/2，保证 a 是 b 的父亲）

【输出格式】

总共一行一个整数，表示答案

【数据规模】

保证树中每个节点至多两个孩子。

20 个测试点，每个测试点 5 分

1.TESTTEST 1~4： N,K <= 10

2.TSETTSET 5~20：N,K <= 1000 数据有梯度且大多随机，尽量优化自己的程序

解析

分别设置f[i][j]和g[i][j]. f[i][j]表示从i出发，不返回i得到j点泡泡气最少天数。

g[i][j]表示最终要返回i，其他和f数组一样，初始化f[i][0]=g[i][0]=0

转移时分两种情况，有一个孩子就直接赋值，两个孩子分两种情况走

Code

#include
      
       #include
       
        #include
        
         using namespace std;const int Size=1000+5;const int INF=1e8;int N,K;int GO[Size][Size];int RE[Size][Size];int child[Size][2];int child_v[Size][2];int sum=0;int read(){    int num=0,w=1;    char ch=getchar();    while(ch<'0' || ch>'9')    {        if(ch=='-') w=-1;        ch=getchar();    }    while(ch<='9' && ch>='0')    {        num=(num<<1)+(num<<3)+ch-'0';        ch=getchar();    }    return num*w;}inline void Init(){    N=read();K=read();    for(int i=1;i
         
          =K)    {        child_v[k][0]=child_v[k][1]=0;        return;    }    if(child[k][0])        DFS1(child[k][0],sum+child_v[k][0]);    if(child[k][1])        DFS1(child[k][1],sum+child_v[k][1]);}void DFS(int k){    GO[k][0]=RE[k][0]=0;    int lc=child[k][0],rc=child[k][1];    if(!lc) return;    DFS(lc);    if(rc) DFS(rc);    int chongjg=child_v[k][0];//走左节点能得到的泡泡气     for(int i=0;i<=K-chongjg;i++)    {        if(GO[lc][i]>INF) break ;         if(GO[lc][i]+1
          
           =0;i--)        //枚举每种情况         {            if(GO[k][i+1]
           
            INF) break; if(GO[rc][i]+1 < GO[k][i+chongjg]) GO[k][i+chongjg]=GO[rc][i]+1; if(RE[rc][i]+2 < RE[k][i+chongjg]) RE[k][i+chongjg]=RE[rc][i]+2; } chongjg=child_v[k][0]+child_v[k][1];//两个节点都走能得到的泡泡气 for(int i=0;i<=K-child_v[k][0];i++) { if(GO[lc][i]>INF) break; for(int j=0;j<=K-chongjg-i;j++) { if(GO[rc][j]>INF) break; if(GO[lc][i]+RE[rc][j]+3
            
             =0;i--) { if(GO[k][i+1]