模拟赛2
调侃一下这次模拟赛爆炸。。。
T1
链接:https://www.luogu.org/problemnew/show/U45562
模拟题.
/*我还是很喜欢你,像风走了八百里不问归期. */
#include <iostream>
#include <cstring>
#include <cstdio>
#define rep(i,x,p) for(int i = x;i <= p;++ i)
const int maxN = 1000 + 7;
char s[maxN][maxN];
int L;
int a[maxN];
int main() {
freopen("curse.in","r",stdin);
freopen("curse.out","w",stdout);
int n;
scanf("%d",&n);
rep(i,1,n)
scanf("%s",s[i] + 1);
L = strlen(s[1] + 1);
rep(j ,1, L) {
int num_1 = 0,num_0 = 0;
rep(i , 1, n)
if(s[i][j] == '1') num_1 ++;
else num_0 ++;
if(num_1 > num_0) a[j] = 1;
}
rep(i,1,L) printf("%d", a[i]);
return 0;
}
T2
神奇的题目,首先看到L满足单调性,二分.
然后剩下的就是如何处理红光和绿光如何使用了.
刚开始思路偏了,感觉是贪心,但是贪心的话,复杂度是(n * log n)的,这就有些说不过去了.
然后开始想DP.设状态的时候一直把法坛加入.复杂度一直是(n^3)的,而且无法优化.
一直想到比赛结束.当时我应该跳出思维.哎。。。。
状态还是比较容易想到.
因为如果(R,G)和的个数大于等于n的话.那么答案就是1.
所以R,G的状态数非常小.
设(f[i][j])表示R使用了i个,G用了j个所能到达的最远处.
然后预处理所有的法坛,跳L步最多到哪,跳2*L步最多跳到哪
这道题就算完成了.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define rep(i,x,p) for(int i = x;i <= p;++ i)
#define sep(i,x,p) for(int i = x;i >= p;-- i)
using namespace std;
const int maxN = 2000 + 7;
int a[maxN],n,R,G;
int f[maxN][maxN]; // f[i][j] 表示红色为i,绿色为j可以到达最远的地方.
int P[maxN],Q[maxN];
inline int read() {
int x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
bool calc(int L)
{
memset(f, 0, sizeof(f));
memset(P, 0, sizeof(P));
memset(Q, 0, sizeof(Q));
rep(i,1,n) {
rep(j,i,n) {
if(a[j] - a[i] + 1 <= L) P[i] = j;
if(a[j] - a[i] + 1 <= 2 * L) Q[i] = j;
}
}
P[n + 1] = Q[n + 1] = n;
rep(i,0,R) {
rep(j,0,G) {
if (i > 0) f[i][j] = max(f[i][j], P[f[i-1][j] + 1]);
if (j > 0) f[i][j] = max(f[i][j], Q[f[i][j-1] + 1]);
}
}
return f[R][G] == n;
}
int main() {
n = read();R = read();G = read();
rep(i,1,n) a[i] = read();
sort(a + 1,a + n + 1);
if(R + G >= n) {puts("1");return 0;}
int l = 1,r = a[n] - a[1] + 1,ans;
while(l <= r) {
int mid = (l + r) >> 1;
if(calc(mid)) {
r = mid - 1;
ans = mid;
}
else l = mid + 1;
}
printf("%d",ans);
return 0;
}
T3
K短路模板,不过我不会.
而且正解也不会证明.
从(1)跑一边最短路,从(n)跑一边最短路,枚举每一条边.
如果这条道路不跟1到n的最短路相通的话.那么就去最小值即可.
#include <iostream>
#include <cstring>
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;
#define rep(i,x,p) for(int i = x;i <= p;++ i)
#define sep(i,x,p) for(int i = x;i >= p;-- i)
const int maxN = 5000 + 7;
const int maxM = 200000 + 7;
int dis[maxN],dis2[maxN];
bool vis[maxN];
typedef pair <int , int > P;
priority_queue<P, vector<P>, greater<P> > Q;
struct Node {
int v,nex,w;
}Map[maxM];
int num,head[maxN];
struct Node_1 {
int u,v,w;
}C[maxM];
void add_Node(int u,int v,int w) {
Map[++ num] = (Node) {v,head[u],w};
head[u] = num;
return;
}
void dij_1(int now) {
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
Q.push(make_pair(0,now));
dis[now] = 0;
while(!Q.empty()) {
int u = Q.top().second;
Q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = head[u];i;i= Map[i].nex) {
int v = Map[i].v;
if(dis[u] + Map[i].w < dis[v]) {
dis[v] = dis[u] + Map[i].w;
Q.push(make_pair(dis[v],v));
}
}
}
return ;
}
void dij_2(int now) {
memset(vis,0,sizeof(vis));
memset(dis2,0x3f,sizeof(dis2));
Q.push(make_pair(0,now));
dis2[now] = 0;
while(!Q.empty()) {
int u = Q.top().second;
Q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = head[u];i;i= Map[i].nex) {
int v = Map[i].v;
if(dis2[u] + Map[i].w < dis2[v]) {
dis2[v] = dis2[u] + Map[i].w;
Q.push(make_pair(dis2[v],v));
}
}
}
return ;
}
inline int read() {
int x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int main() {
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
int n = read(),m = read() ;
int u , v, w;
rep(i,1,m) {
u = read();v = read();w = read();
add_Node(u,v,w);
add_Node(v,u,w);
C[i] = (Node_1) {u,v,w};
}
dij_1(1);
dij_2(n);
int tmp = dis[n];
int ans = 0x3f3f3f3f;
rep(i,1,m) {
int u = C[i].u,v = C[i].v,w = C[i].w;
if(dis[u] + dis2[v] + w != tmp) {
ans = min(ans,dis[u] + dis2[v] + w);
}
if(dis2[u] + dis[v] + w != tmp) {
ans = min(ans,dis2[u] + dis[v] + w);
}
}
printf("%d",ans);
return 0;
}
Last
这次比赛直接sb了,没什么好讲的.除了T2有价值,其余的全都是傻逼题.
放在PJ还可以.