7.22杭电多校第二场

过5题,最后一小时产能爆炸,rk180,属于是爆炸了

我签了1012,1005,后续写了1008和1011,中间1004我想了莫队+trie,但是没写

1005

题意:

给n个字符,依次添加进字符串。每次可以添加到当前串的首或者尾。要求最终串的字典序最小。求使得最终串字典序最小的添加方案数。

n<=10^5

题解:

先考虑字典序最小的字符,找出这些字符的第一次出现的位置,可以发现,这个第一次出现的位置之后的放置方式是唯一的。

考虑剩下的部分,依旧是找字典序最小的字符...

最终结果就是相同连续前缀的长度的2的次幂。

代码:

 1 //下次一定换个二次元队名捏 
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 const int mo=1e9+7;
 5 int ksm(int x,int y)
 6 {
 7     int ret=1;
 8     while (y)
 9     {
10         if (y&1) ret=1ll*ret*x%mo;
11         x=1ll*x*x%mo;
12         y=y>>1;
13     }
14     return ret;
15 }
16 int main()
17 {
18     int t;
19     scanf("%d",&t);
20     while (t)
21     {
22         t--;
23         int n;
24         scanf("%d",&n); 
25         char s[200020];
26         scanf("%s",s+1);
27         int ll=0;
28         for (int i=1;i<n;i++) if (s[i]!=s[i+1])
29         {
30             ll=i;
31             break;    
32         }
33         if (!ll) ll=n;
34         printf("%d\n",ksm(2,ll-1));
35     }
36 }

 

1008

题意:

n门课,m种学习资料,花费a[i]时间可以提示某门课b[i]的分数,在t时间内,最多挂p科的情况下,求最高总分

n<=50 m<=15000 t<=500 p<=3

题解:

一开始想枚举挂科数,后来发现大可不必。

设g[i][j][k]表示前i科花j天时间挂k科的情况下的最高总分

预处理一个f[i][j]表示第i科达到j分的最少天数

预处理的过程是O(100m)的

总复杂度是O(100ntp)

代码:

  1 //下次一定换个二次元队名捏 
  2 #include<bits/stdc++.h>
  3 using namespace std;
  4 char s[100][100];
  5 int ss[100];
  6 struct aa
  7 {
  8     int x,y,z;    
  9 }e[100010];
 10 bool cmp(aa x,aa y)
 11 {
 12     return x.x<y.x;
 13 }
 14 int b[100010],c[100010];
 15 int f[100][200];
 16 int g[100][600][5];
 17 int main()
 18 {
 19     int t;
 20     scanf("%d",&t);
 21     while (t)
 22     {
 23         t--;
 24         int n;
 25         scanf("%d",&n);
 26         for (int i=1;i<=n;i++) scanf("%s",s[i]+1),ss[i]=strlen(s[i]+1);
 27         int m;
 28         scanf("%d",&m);
 29         for (int i=1;i<=m;i++)
 30         {
 31             int x,y,z;
 32             char s1[30];
 33             scanf("%s",s1+1);
 34             int py=strlen(s1+1);
 35             for (int j=1;j<=n;j++) 
 36             {
 37                 if (ss[j]==py)
 38                 {
 39                     int fl=1;
 40                     for (int k=1;k<=py;k++) if (s[j][k]!=s1[k]) fl=0;
 41                     if (fl)
 42                     {
 43                         x=j;
 44                         break;    
 45                     }
 46                 }
 47             }
 48             scanf("%d%d",&y,&z);
 49             e[i].x=x;
 50             e[i].y=y;
 51             e[i].z=z;
 52         }
 53         sort(e+1,e+m+1,cmp);
 54         e[m+1].x=0;
 55         int last=1;
 56         int tt,pp;
 57         scanf("%d%d",&tt,&pp);
 58         for (int i=0;i<=n;i++) for (int j=0;j<=tt;j++) for (int k=0;k<=pp;k++) g[i][j][k]=-100000000;
 59         for (int i=1;i<=m;i++)
 60         {
 61             if (e[i].x!=e[i+1].x)
 62             {
 63                 int ww=e[i].x,k=0;
 64                 for (int j=last;j<=i;j++) b[++k]=e[j].y,c[k]=e[j].z;
 65                 last=i+1;
 66                 for (int j=1;j<=100;j++) f[ww][j]=510;
 67                 f[ww][0]=0;
 68                 for (int j=1;j<=k;j++) for (int l=100;l>=b[j];l--) f[ww][l]=min(f[ww][l-b[j]]+c[j],f[ww][l]);
 69                 if (ww==1) for (int j=0;j<=100;j++) 
 70                 {
 71                     if (j<60) g[1][f[1][j]][1]=j;
 72                     else g[1][f[1][j]][0]=j;    
 73                 }
 74             }
 75         }
 76         for (int i=1;i<n;i++)
 77         {
 78             for (int j=0;j<=tt;j++) 
 79             {
 80                 for (int k=0;k<=pp;k++)
 81                 {
 82                     if (g[i][j][k]>=0)
 83                     {
 84                         for (int l=0;l<=100;l++)
 85                         {
 86                             if (f[i+1][l]+j<=tt)
 87                             {
 88                                 if (l<60&&k!=pp) g[i+1][j+f[i+1][l]][k+1]=max(g[i+1][j+f[i+1][l]][k+1],g[i][j][k]+l);
 89                                 if (l>=60) g[i+1][j+f[i+1][l]][k]=max(g[i+1][j+f[i+1][l]][k],g[i][j][k]+l);
 90                             }
 91                         }
 92                     }
 93                 }
 94             }
 95         }
 96         int ans=-1;
 97         for (int i=0;i<=tt;i++) for (int j=0;j<=pp;j++) ans=max(ans,g[n][i][j]);
 98         printf("%d\n",ans);
 99     }
100 }

 

1011

题意:

给两个长度为n的数组a和b,下标从0开始

c[k]=max(a[i]*a[j]) (i&j>=k)

求c[i]的和(0<=i<n)

题解:

可以把a[i]的值传递到a[j]处,只要j是i二进制下的子集,这样做不会影响答案。

所以对0~n-1按二进制位数排序,将值一直传递即可。

因为有正负数,存一个最大值和一个最小值,注意考虑结果为负数的情况。

代码:

 1 //下次一定换个二次元队名捏 
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 const int mo=998244353;
 5 const int N=3e5+10;
 6 int a[N],a1[N],b[N],b1[N],cc[N],id[N];
 7 long long c[N];
 8 bool cmp(int x,int y)
 9 {
10     return cc[x]>cc[y];    
11 }
12 void ww()
13 {
14     int n;
15     scanf("%d",&n);
16     for (int i=0;i<n;i++) scanf("%d",&a[i]),a1[i]=a[i];
17     for (int i=0;i<n;i++) scanf("%d",&b[i]),b1[i]=b[i];
18     for (int i=1;i<=n;i++) id[i]=i-1;
19     sort(id+1,id+n+1,cmp);
20     for (int i=1;i<=n;i++)
21     {
22         c[id[i]]=max(1ll*a1[id[i]]*b[id[i]],max(1ll*a[id[i]]*b1[id[i]],max(1ll*a[id[i]]*b[id[i]],1ll*a1[id[i]]*b1[id[i]])));
23         for (int j=1;j<=id[i];j=j*2)
24         {
25             if (j&id[i]) 
26             {
27                 a[id[i]-j]=max(a[id[i]-j],a[id[i]]);
28                 a1[id[i]-j]=min(a1[id[i]-j],a1[id[i]]);
29                 b[id[i]-j]=max(b[id[i]-j],b[id[i]]);
30                 b1[id[i]-j]=min(b1[id[i]-j],b1[id[i]]);
31             }
32         }
33     }
34     long long ans=(c[n-1]%mo+mo)%mo;
35     long long mx=c[n-1];
36     //printf("%lld\n",mx);
37     for (int i=n-2;i>=0;i--) mx=max(mx,c[i]),ans=((ans+mx)%mo+mo)%mo;//,printf("%lld\n",mx);
38     printf("%lld\n",ans);
39 }
40 int main()
41 {
42     //freopen("test.in","r",stdin);
43     for (int i=0;i<=1000000;i++) 
44     {    
45         int x=i;
46         while (x)
47         {
48             x=x-(x&(-x));
49             cc[i]++;    
50         }
51     }
52     int t;
53     scanf("%d",&t);
54     while (t)
55     {
56         t--;
57         ww();    
58     }
59 }

 

上一篇:Exchange批量迁移用户到指定邮箱数据库


下一篇:java8新特性:利用Lambda处理List集合