今天，是一个重要的日子。

(想什么呢？我说的当然是那位大人的生日啦)

 

T1 题意简述：

 

Description

Input

Output

输出 q行，第 i行输出对于第 i个询问的答案。

Data Constraint

 

   解题思路：出题人居然已经懒到用河北2013年的省选题当考题了...

             而且重点是还把HEOI打成HBOI(湖北OI)了...

             这道题怎么做不用我多说了吧。

             正反各做一遍背包，二进制拆分优化即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,k,ans,mon[1001],wei[1001],tim[1001];int dp1[1001][1001],dp2[1001][1001];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&mon[i],&wei[i],&tim[i]); for(int i=1;i<=n;i++) { int lim=tim[i]; for(int j=0;j<=1000;j++) dp1[i][j]=dp1[i-1][j]; for(int j=1;lim;j=min(j<<1,lim)) { for(int l=1000;l>=j*mon[i];l--) dp1[i][l]=max(dp1[i][l],dp1[i][l-j*mon[i]]+j*wei[i]); lim-=j; } } for(int i=n;i>=1;i--) { int lim=tim[i]; for(int j=1;j<=1000;j++) dp2[i][j]=dp2[i+1][j]; for(int j=1;lim;j=min(j<<1,lim)) { for(int l=1000;l>=j*mon[i];l--) dp2[i][l]=max(dp2[i][l],dp2[i][l-j*mon[i]]+j*wei[i]); lim-=j; } } scanf("%d",&k); for(int i=1;i<=k;i++) { int u,v; scanf("%d%d",&u,&v); u++; ans=0; for(int j=0;j<=v;j++) ans=max(ans,dp1[u-1][j]+dp2[u+1][v-j]); printf("%d\n",ans); } return 0;}
          
         
        
       
      
     

 

---

 

T2 题意简述：

 

Description

陪审团制度历来是司法研究中的一个热议话题，由于陪审团的成员组成会对案件最终的结果产生巨大的影响，诉讼双方往往围绕陪审团由哪些人组成这一议题激烈争夺。 小 W 提出了一个甲乙双方互相制衡的陪审团成员挑选方法：假设共有 n 名候选陪审团成员，则由甲先提名 s 位候选人，再由乙在甲提名的 s 位候选人中选出 t 名，作为最终的陪审团成员。显然这里应当有n ≥ s ≥ t。假设候选人 k 对甲、乙的有利程度都可以用一个二元组(??, ??)来表示，??越大说明候选人 k 对甲越有利，??越大则对乙越有利。在此前提下，双方的目标都变得明确：甲要最大化最终陪审团 t 人的 x 之和，最小化 y之和，乙则反之。 现在甲方决定聘请你为律师，并且事先得知了乙方律师的策略：乙方律师会在你提名的 s 名候选人中选出 t 名使得这 t 人的 y 值之和最大，再保证 y 值之和最大的前提下使得 x 值之和尽量小(在对乙方最有利的前提下对甲方最不利)。 现在你应当慎重地提名 s 位候选人使得最终由乙方律师确定的 t 人 x 值和最大，若有多种方案，则应再使被乙方排除掉的 s-t人的 y 值和尽量大，在此基础上最大化 s 人的 x 值 之和,在此基础上最小化 s 人的 y 值 之和。 你的当事人并不关心你提名的具体是哪些人，只要你告诉他你提名的 s 人的 x 值之和 与 y 值之和。

Input

第一行包含三个整数 n,s,t。 接下来 n 行，每行两个整数分别表示??, ??。

Output

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

Data Constraint

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

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

对于 100%的测试数据? ≤ 100000, ?, ? ≤ 1000000

 

   解题思路：思路有点绕的贪心。

             首先挑出所有可能成为陪审团成员之一的人。

             对Y最优的情况：yk最大的t个人都在备选行列内。

                            此时Y可以挑这t个yk最大的人。

             对Y最劣的情况：yk最大的n-s个人都不在备选行列内。

                            此时Y只能挑yk排名从n-s+1到n-s+t这t个人。

             因此yk值排名前n-s+t个人都有可能成为陪审团成员之一。

             在第一次排序中若yk值相同，则按xk值从小到大排列。

             因为Y的策略是保证yk值最大的前提下使xk值最小，因此若最后几个人yk值都相同，Y会挑xk

             值小的，而xk值大的并没有被挑走的可能。

 

             然后把这n-s+t个人按xk从大到小排序，我们要让排名前t个人成为陪审团。

             让他们成为陪审团有一定条件：

             备选队列里的其他人yk值必须严格小于陪审团成员yk值的最小值。

             为什么不能等于？因为若yk值相等，Y就会挑xk值小的。除非xk，yk这两个值均相同，否则

             陪审团总xk值就会变小。

             为了让Y排除掉的那s-t个人yk值尽量大，我们需要让陪审团成员yk值尽量大。

             因此第二次排序时若xk值相同，就按yk值从大到小排列。

            

             接下来要从剩下的n-t个人中挑选那s-t个人。

             因为要使Y排除掉的那s-t个人yk值尽量大，因此我们按yk值从大到小排序。

             同时我们还要使备选成员的xk值总和尽量大，因此yk值相同时按xk值从大到小排列。

             选出前s-t个人即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define INF 0x3f3f3f3f#define ll long longusing namespace std;ll n,s,t,cnt,ansx,ansy;struct uio{ ll vx,vy;}peo[100001],peo1[100001];bool cmp1(uio x,uio y){ if(x.vy==y.vy) return x.vx
           
            y.vy;}bool cmp2(uio x,uio y){ if(x.vx==y.vx) return x.vy>y.vy; return x.vx>y.vx;}bool cmp3(uio x,uio y){ if(x.vy==y.vy) return x.vx>y.vx; return x.vy>y.vy;}int main(){ scanf("%lld%lld%lld",&n,&s,&t); for(ll i=1;i<=n;i++) scanf("%lld%lld",&peo[i].vx,&peo[i].vy); sort(peo+1,peo+1+n,cmp1); sort(peo+1,peo+1+n-s+t,cmp2); ll mnx=INF,mny=INF,mxx=-1,mxy=-1; for(ll i=1;i<=t;i++) { ansx+=peo[i].vx,ansy+=peo[i].vy; mnx=min(mnx,peo[i].vx),mny=min(mny,peo[i].vy); mxx=max(mxx,peo[i].vx),mxy=max(mxy,peo[i].vy); } for(ll i=1;i<=n;i++) if(peo[i].vy
           
          
         
        
       
      
     

 

---

 

T3 题意简述：

 

Description

科学家温斯顿从数据库中找到了一串相当长的字符串。

他正试图用一个模板串来重构这个字符串。

他可以将模板串复制多份，通过合适的方式拼接起来，使得最终的串与原串一致。

如果两个模板串互相覆盖，那么覆盖的部分必须完全一致。

原串的所有位置必须被覆盖到。

显然，原串本身就是一个模板串。但为了节省成本，他想找到长度最短的模板串。

Input

第一行一个仅由小写字母构成的字符串。

Output

第一行一个整数，表示模板串的最小长度。

Data Constraint

设字符串的长度为N。

Subtask1[20pts]:N<=100

Subtask2[30pts]:N<=25000

Subtask3[50pts]:N<=500000

 

   解题思路：一道KMP瞎搞的题，也可以用dp。这里介绍dp做法。

             当然，字符串匹配的题要先把next数组求出来。

             设dp[i]表示能完全覆盖前缀i的最短前缀的长度。

             发现dp[i]最多只有2种取值：i或是dp[next[i]]。

             因为能完全覆盖一个字符串a的字符串b必同时是a的前缀和后缀。

             考虑何时dp[i]=dp[next[i]]。

             显然，最后next[i]个字符是肯定要被一个长为next[i]的前缀覆盖的。

             除去这next[i]个字符，前面的字符要用若干个前缀覆盖。

             为保证完全覆盖，覆盖前i-next[i]个字符的最后一个前缀与覆盖从第i-next[i]+1个字符到

             第i个字符的这个前缀必然是首尾相接或是有重合部分的。如下图所示：

             因此只需在[i-next[i],i]区间内找有没有dp[j]=dp[next[i]]的。

             有则dp[i]=dp[next[i]]，否则dp[i]=i。

             每次转移时都找一遍太慢了，只需开数组mx[i]记录dp[j]=i的最大的j即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,next[500001],dp[500001],mx[500001];char s[500001];void getnxt(){ int num=0; for(int i=2;i<=n;i++) { while(num&&s[num+1]!=s[i]) num=next[num]; if(s[num+1]==s[i]) num++; next[i]=num; }}int main(){ scanf("%s",s+1); n=strlen(s+1); getnxt(); for(int i=1;i<=n;i++) { if(mx[dp[next[i]]]>=i-next[i]) dp[i]=dp[next[i]]; else dp[i]=i; mx[dp[i]]=i; } printf("%d\n",dp[n]); return 0;}