本来应该认真做这场的。思路都是正确的。
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;
}