codeforces round #257 div2 C、D「建议收藏」

codeforces round #257 div2 C、D

大家好,又见面了,我是全栈君。

本来应该认真做这场的大笑。思路都是正确的。

C题,是先该横切完或竖切完,无法满足刀数要求。再考虑横切+竖切(竖切+横切),

  由于横切+竖切(或竖切+横切)会对分割的东西产生交叉份数。从而最小的部分不会尽可能的大。  

         代码例如以下。尽管比較长、比較乱,但全然能够压缩到几行,由于差点儿是4小块反复的代码,自己也懒得压缩

         注意一点,比方要推断最小块的时候,比方9行要分成2份,最小的剩下那份不是9取模2,而应该是4

m/(k+1)<=m-m/(k+1)*k

 

        

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1e6+10;
const LL MOD = 1e9+7;
LL f[1000];
int main() {
    LL n,m,k;
    //freopen("in.txt", "r", stdin);
    while(scanf("%I64d %I64d %I64d",&n,&m, &k)==3) {
        if(k > (n+m-2)) { printf("-1\n"); continue;}
        LL k1 = k;
        LL ans = 0, ans2 = 0;
        if(1){
            if(k<=(m-1)){
              if(m%(k+1)==0)
                ans = m/(k+1)*n;
              else if(m/(k+1)<=m-m/(k+1)*k) {
                ans = m/(k+1)*n;
              }
              else ans = (m/(k+1)-1)*n;
            }
            else {
                k -= (m-1);
                if(n%(k+1)==0)
                    ans = n/(k+1);
                else if(m/(k+1)<=m-m/(k+1)*k) {
                    ans = n/(k+1);
                }
                else ans = (n/(k+1)-1);
            }
        }
        //printf("%I64d~\n", ans);
        swap(n, m);
        if(2){
            k = k1;
            if(k<=(m-1)){
              if(m%(k+1)==0) {
                ans2 = m/(k+1)*n;
              }
              else if(m/(k+1)<=m-m/(k+1)*k) {
                ans2 = m/(k+1)*n;
              }
              else ans2 = (m/(k+1)-1)*n;
            }
            else {
                k -= (m-1);
                if(n%(k+1)==0)
                    ans2 = n/(k+1);
                else if(m/(k+1)<=m-m/(k+1)*k) {
                    ans2 = n/(k+1);
                }
                else ans2 = (n/(k+1)-1);
            }
        }

        printf("%I64d\n", max(ans, ans2));
    }
}



D题

一看题目时就非常欣喜,挺有意思的图论。

一開始的思路是错的,每次进行松弛操作时推断当前边是否标记过。从而进行减减操作。这样考虑忘了后面可能进行了一些更新,从而覆盖了前面的标记

正确思路:

在每次优先队列出点的时候,推断从起点到这个点的最短路有多少是跟K条(train route)是反复的就可以

自己须要注意的地方:

1、如何记录最短路的数目

2、当k==Count[u]时候的处理

 3、小细节,第一个节点u,tt与Count[u]都是等于0的

代码还是挺快的~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define clr(x) memset(x,0,sizeof(x))
#define fp1 freopen("in.txt","r",stdin)
#define fp2 freopen("out.txt","w",stdout)
#define pb push_back

#define INF 0x3c3c3c3c
typedef long long LL;

const int maxn = 4*1e5;
bool vis[maxn];
struct Edge {int from,to,dist,cnt;};
struct Node
{
    int d,u;
    bool operator <(const Node &a) const {
        return a.d<d;   //从小到大排序。

}};int n,m,k; //点数和边数,用n表示,e不能和m冲突vector<Edge> edges;//边列表vector<int> G[maxn];//每一个结点出发的边编号(从0開始编号)vector<int> qw[maxn];int Count[maxn];bool done[maxn];//是否已永久编号int d[maxn];//s到各个点的距离int p[maxn];//最短路中的上一条边void init(){ for(int i=0;i<n;i++) G[i].clear();//清空邻接表 edges.clear();}void addedge(int from,int to,int dist)//假设是无向。每条无向边需调用两次addedge{ edges.push_back((Edge){from,to,dist}); int temp=edges.size(); G[from].push_back(temp-1);}void dijk(int s){ clr(Count); priority_queue<Node> q; for(int i=0;i<n;i++) d[i]=INF; d[s]=0; memset(done,0,sizeof(done)); q.push((Node){0,s}); while(!q.empty()) { Node x=q.top(); q.pop(); int u=x.u; if(done[u]) continue; done[u]=true; for(int i=0;i<G[u].size();i++) { Edge &e=edges[G[u][i]]; if(d[e.to]>d[u]+e.dist) { d[e.to]=d[u]+e.dist; p[e.to]=G[u][i]; q.push((Node){d[e.to],e.to}); Count[e.to] = 1; } else if(d[e.to]==d[u]+e.dist){ Count[e.to] ++; } } int tt = 0; for(int i = 0;i < qw[u].size();i++){ if(qw[u][i] > d[u]) { //printf("%d %d %d~\n", u, qw[u][i], d[u]); int temp = k -1; k = temp; } else if(qw[u][i] == d[u]) tt++; } //printf("%d %d %d!\n", u, tt, Count[u]); if(tt == 0) continue; else if(tt < Count[u]) { k -= tt; } else if(tt == Count[u]) k -= (tt-1); }}int main(){ //fp1; while(scanf("%d %d %d", &n, &m, &k) == 3){ int k1 = k; init(); int u, v, w; for(int i = 1;i <= m;i++){ scanf("%d %d %d", &u, &v, &w); u--; v--; addedge(u, v, w); addedge(v, u, w); } for(int i = m+1;i <= m+k;i++){ scanf("%d %d", &u, &v); u--; addedge(0, u, v); addedge(u, 0, v); qw[u].pb(v); } dijk(0); printf("%d\n", k1 - k); } return 0;}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115280.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 深挖洞广积粮不称霸_threadlocal源码

    深挖洞广积粮不称霸_threadlocal源码ThreadLocal是什么早在JDK1.2的版本中就提供java.lang.ThreadLocal,ThreadLocal为解决多线程程序的并发问题提供了一种新的思路。使用这个工具类可以很简洁地编写出优美的多线程程序。ThreadLocal很容易让人望文生义,想当然地认为是一个“本地线程”。其实,ThreadLocal并不是一个Thread,而是Thread的局部变量,也许把它

  • VUE父子组件之间的传值,以及兄弟组件之间的传值;

    VUE父子组件之间的传值,以及兄弟组件之间的传值;一、Vue父子组件之间传值vue使用中,经常会用到组件,好处是:1、如果有一个功能很多地方都会用到,写成一个组件就不用重复写这个功能了;2、页面内容会简洁一些;方便管控;子组件的传值是通过props来传递数据,$emit来触发事件;下面是一个简单的子组件props传值:父组件的部分:首先引入组件,在组件上绑定你要传给组件的值;然后,在组件里通过props来接收你从父页面传…

  • useGeneratedKeys属性

    useGeneratedKeys属性Springboot中Mybatis配置文件Mapper参数useGeneratedKeys=“true”keyProperty=“id”useGeneratedKeys设置为true时,表示如果插入的表id以自增列为主键,则允许JDBC支持自动生成主键,并可将自动生成的主键id返回…

  • anaconda安装python模块_保姆号必须一个区

    anaconda安装python模块_保姆号必须一个区Python固然通俗优雅,适合新手入门,但其有两个痛点:依赖网复杂、包管理混乱,为了更好地管理Python库,引入Anaconda。本文介绍Anaconda全套配置流程与工作中常用的命令速查表,提升开发效率

    2022年10月21日
  • pycharm 2022最新永久激活码【中文破解版】

    (pycharm 2022最新永久激活码)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~ML…

  • PCI设备驱动程序「建议收藏」

    PCI设备驱动程序「建议收藏」PCI总线是现在非常流行的计算机总线,学会它的驱动设计方法很重要。相信曾经想学习PCI总线驱动的人有这么一个经历,就是去看那些讲解PCI总线驱动的书籍和资料的时候,会被里面繁杂的内容所击败,又是什么配置空间又是什么枚举的,还没开始真正的去写PCI的驱动,到这里就已经开始打退堂鼓了。其实,只要你认真下去,虽然有些东西看不明白,但是对于你写PCI的驱动来说,似乎“不那么重要”。因为,Linux内核对P…

    2022年10月25日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号