• 2022/8/12

    ​

    活动地址：CSDN21天学习挑战赛

    1466D - 13th Labour of Heracles

    一看以为这是树的题目，但其实是比较水的，观察一下可以发现加了另外一个颜色后非叶子节点会多加一遍，所以我们优先让权值大的多加一遍，这个点的权值可以加的次数是这个点的度数-1，这题就做完了，统计度数之后从大到小依次加就行

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. #include
    16. //HDU火车头
    17. //#include 
    18. #define ll long long
    19. #define lowbit(x) ((x)&(-x))
    20. using namespace std;
    21. int mod=1e9+7;
    22. double eps=1e-8;
    23. ll t,n,in[200005];
    24. struct node{
    25.     ll id,val;
    26.     bool operator<(const node& a) const{
    27.         return val>a.val;
    28.     }
    29. }w[200005];
    30. int main(){
    31.     scanf("%lld",&t);
    32.     while(t--){
    33.         scanf("%lld",&n);
    34.         ll sum=0;
    35.         for(int i=1;i<=n;i++) scanf("%lld",&w[i].val),sum+=w[i].val,w[i].id=i;
    36.         for(int i=1;i
    37.             ll u,v;
    38.             scanf("%lld%lld",&u,&v);
    39.             in[u]++;in[v]++;
    40.         }
    41.         sort(w+1,w+n+1);
    42.         printf("%lld ",sum);
    43.         for(int i=1;i<=n;i++){
    44.             while(in[w[i].id]>1){
    45.                 sum+=w[i].val;
    46.                 printf("%lld ",sum);
    47.                 in[w[i].id]--;
    48.             }
    49.         }
    50.         printf("\n");
    51.         for(int i=1;i<=n;i++) in[i]=0;
    52.     }
    53.     system("pause");
    54.     return 0;
    55. }
    56.

    P6140 [USACO07NOV]Best Cow Line S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

    这题的数据较弱直接暴力就能过，首尾比较每次都先放小的，如果相等的话就去前面比较，一直比到不相等为止，然后在判断哪个小就放哪个，如果都相等就随便放

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. #include
    16. //HDU火车头
    17. //#include 
    18. #define ll long long
    19. #define lowbit(x) ((x)&(-x))
    20. using namespace std;
    21. int mod=1e9+7;
    22. double eps=1e-8;
    23. ll n,m;
    24. char s[500005];
    25. bool cmp(ll l,ll r){
    26.     while(s[l]==s[r]&&l
    27.     if(lreturn s[l]
    28.     else return 1;
    29. }
    30. int main(){
    31.     scanf("%lld",&n);
    32.     for(int i=1;i<=n;i++) cin>>s[i];
    33.     ll l=1,r=n,cnt=0;
    34.     while(l<=r){
    35.         if(s[l]
    36.         else if(s[l]>s[r]){cout<
    37.         else{
    38.             if(cmp(l,r)){cout<
    39.             else{cout<
    40.         }
    41.         if(cnt>=80){printf("\n");cnt=0;}
    42.     }
    43.     system("pause");
    44.     return 0;
    45. }
    46.

    1519D - Maximum Sum of Products 区间dp

    感觉之前做过类似的，然后就疯狂的想试一试之前的结论管不管用，然后试了半天也不对，最后看题解是区间dp，，，dp[i][j]表示i到j这块区间反转，c[i]表示前缀和，转移也很好转移，dp[i][j]=dp[i+1][j-1]+a[j]*b[i]+a[i]*b[j],就是由小区间转移到大区间，枚举长度和起点就可以了

    D. Maximum Sum of Products（前缀和 + 区间dp)_青山_12的博客-CSDN博客

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. #include
    16. //HDU火车头
    17. //#include 
    18. #define ll long long
    19. #define lowbit(x) ((x)&(-x))
    20. using namespace std;
    21. int mod=1e9+7;
    22. double eps=1e-8;
    23. ll n,a[5005],b[5005],c[5005],dp[5005][5005];
    24. int main(){
    25.     scanf("%lld",&n);
    26.     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    27.     for(int i=1;i<=n;i++) scanf("%lld",&b[i]),c[i]=c[i-1]+a[i]*b[i],dp[i][i]=a[i]*b[i];
    28.     ll ans=c[n];
    29.     for(int len=1;len
    30.     for(int i=1;i+len<=n;i++){
    31.         ll j=i+len;
    32.         dp[i][j]=dp[i+1][j-1]+a[j]*b[i]+a[i]*b[j];
    33.         ll sum=dp[i][j]-(c[j]-c[i-1])+c[n];
    34.         ans=max(ans,sum);
    35.     }
    36.     printf("%lld\n",ans);
    37.     system("pause");
    38.     return 0;
    39. }
    40.

    B-Gaming_牛客小白月赛54 (nowcoder.com) 差分

    淦，从出发点就想错了，想成了区间覆盖，丫的根本就不是，因为他只需要不要一个debuff就可以了，就可以去枚举不要那个损失最少，把区间的s[i]都加到每个点上，然后总和减去最小的点就可以

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. #include
    16. //HDU火车头
    17. //#include 
    18. #define ll long long
    19. #define lowbit(x) ((x)&(-x))
    20. using namespace std;
    21. int mod=1e7+7;
    22. double eps=1e-8;
    23. ll n,m,b[1000006];
    24. int main(){
    25.     scanf("%lld%lld",&n,&m);
    26.     ll minn=1e18,ans=0;
    27.     for(int i=1;i<=n;i++){
    28.         ll x,y,z;
    29.         scanf("%lld%lld%lld",&x,&y,&z);
    30.         b[x]+=z;b[y+1]-=z;
    31.         ans+=z;
    32.     }
    33.     for(int i=1;i<=m;i++) b[i]+=b[i-1];
    34.     for(int i=1;i<=m;i++) minn=min(minn,b[i]);
    35.     printf("%lld\n",ans-minn);
    36.     system("pause");
    37.     return 0;
    38. }
    39.

    C-School_牛客小白月赛54 (nowcoder.com)

    c题很直白，唯一卡住的点就是应该把这些时段能合并的合并，不然r是无序的， 二分出来可能是错误的答案

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. #define lowbit(i) ((i)&(-i))
    5. const ll mod=1e9+7;
    6. double eps=1e-8;
    7. ll n,h,m,q;
    8. struct node{
    9.     ll l,r;
    10.     bool operator<(const node &a) const{
    11.         return r
    12.     }
    13. }v[1005],u[1005];
    14. bool cmp(node &a,node &b){
    15.     if(a.l==b.l) return a.r
    16.     return a.l
    17. }
    18. int main(){
    19.     scanf("%lld%lld%lld%lld",&n,&h,&m,&q);
    20.     for(int i=1;i<=n;i++){
    21.         ll a,b,c,d;
    22.         scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    23.         v[i].l=(a)*m+b;
    24.         v[i].r=(c)*m+d;
    25.     }
    26.     sort(v+1,v+n+1,cmp);
    27.     ll cnt=1;u[1]=v[1];
    28.     for(int i=2;i<=n;i++){
    29.         if(u[cnt].r
    30.         else{
    31.             u[cnt].r=max(u[cnt].r,v[i].r);
    32.         }
    33.     }
    34.     while(q--){
    35.         ll x,y;
    36.         scanf("%lld%lld",&x,&y);
    37.         node tmp;
    38.         tmp.l=(x)*m+y;
    39.         tmp.r=(x)*m+y;
    40.         ll id=lower_bound(u+1,u+cnt+1,tmp)-u;
    41.         //cout<
    42.         if(id>cnt) printf("Yes\n");
    43.         else{
    44.             if(tmp.l>=u[id].l) printf("No\n");
    45.             else printf("Yes\n");
    46.         }
    47.     }
    48.     system("pause");
    49.     return 0;
    50. }

    D-Word_牛客小白月赛54 (nowcoder.com)

    把能互相转移的两个点之间建一条边，然后跑最短路就可以了，还是个板子，淦，让B卡住了，没想到c和d也不难

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. #define lowbit(i) ((i)&(-i))
    5. const ll mod=1e9+7;
    6. double eps=1e-8;
    7. ll n,m;
    8. ll ss=0,tt=0,dist[20005],pre[20005],vis[20005];
    9. string a[20005],s,t;
    10. ll head[40010],cnt;
    11. struct Edge{
    12.     ll from,to,dis,next;
    13. }edge[40010];
    14. void addedge(ll from,ll to,ll w){
    15.     edge[++cnt].from=from;
    16.     edge[cnt].to=to;
    17.     edge[cnt].dis=w;
    18.     edge[cnt].next=head[from];
    19.     head[from]=cnt;
    20. }
    21. bool pd(string s1,string s2){
    22.     ll res=0;
    23.     for(int i=0;i
    24.     if(s1[i]!=s2[i]) res++;
    25.     return res==1;
    26. }
    27. struct node{
    28.     ll id,dis;
    29.     bool operator<(const node& x) const{
    30.         return x.dis
    31.     }
    32. };
    33. void print(ll s,ll t){
    34.     if(s==t){cout<"\n";return;}
    35.     print(s,pre[t]);
    36.     cout<"\n";
    37. }
    38. void bfs(){
    39.     for(int i=1;i<=n;i++) dist[i]=1e18;
    40.     for(int j=1;j<=n;j++) vis[j]=0;
    41.     dist[ss]=0;
    42.     priority_queueq;
    43.     q.push(node{ss,0});
    44.     while(!q.empty()){
    45.         node u=q.top();q.pop();
    46.         ll now=u.id;
    47.         if(vis[now]) continue;
    48.         vis[now]=1;
    49.         for(int i=head[now];i;i=edge[i].next){
    50.             ll j=edge[i].to;
    51.             if(dist[now]+edge[i].dis
    52.                 dist[j]=dist[now]+edge[i].dis;
    53.                 if(!vis[j]) q.push(node{j,dist[j]});
    54.                 pre[j]=now;
    55.             }
    56.         }
    57.     }
    58.     if(dist[tt]==1e18){
    59.         printf("-1\n");
    60.     }
    61.     else{
    62.         printf("%lld\n",dist[tt]-1);
    63.         print(ss,tt);
    64.     }
    65. }
    66. int main(){
    67.     scanf("%lld%lld",&n,&m);
    68.     for(int i=1;i<=n;i++) cin>>a[i];
    69.     cin>>s>>t;
    70.     if(s==t){
    71.         cout<<0<<"\n"<"\n"<"\n";
    72.         return 0;
    73.     }
    74.     for(int i=1;i<=n;i++){
    75.         if(a[i]==s) ss=i;
    76.         if(a[i]==t) tt=i;
    77.     }
    78.     if(!ss) a[++n]=s,ss=n;
    79.     if(!tt) a[++n]=t,tt=n;
    80.     for(int i=1;i<=n;i++)
    81.     for(int j=1;j<=n;j++){
    82.         if(i==j) continue;
    83.         if(pd(a[i],a[j])) addedge(i,j,1),addedge(j,i,1);
    84.     }
    85.     bfs();
    86.     system("pause");
    87.     return 0;
    88. }

  • 相关阅读:
    自学Python第十天- 异常
    网络安全（黑客）——2024自学
    redis缓存穿透、击穿、雪崩
    【Python数据结构与算法】线性结构小结
    Win10右键 nvidia rtx desktop manager 怎么删除（最新）
    使用招商银行云直连服务提现(.Net6)
    Nignx部署前端页面
    JS实现二叉排搜索树
    【STM32】基本定时器
    NISP-SO网络安全运维是什么？安全运维工程师
  • 原文地址：https://blog.csdn.net/weixin_52621204/article/details/126304094