slove 6/11

A.夺宝奇兵

Code:zz

Thinking:zz

贪心即可。这条路线里,点n1和点n2肯定是相连的,接下来,点(n-1)1和点(n-1)2分别是和n1和点n2相连的,一共有两种情况,选择距离短的即可,就这样一直往前贪心。

//#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<math.h>
#include<cmath>
#include<time.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>
#include<numeric>
#include<stack>
#include<bitset>
#include<unordered_map>
const int maxn = 0x3f3f3f3f;
const double EI = 2.71828182845904523536028747135266249775724709369995957496696762772407663035354594571382178525166427;
const double PI = 3.141592653589793238462643383279;
using namespace std;
struct s
{
long long x1,y1,x2,y2;
}z[];
inline long long dis(long long x1,long long y1, long long x2,long long y2)
{
long long z1 = x1 - x2;
long long z2 = y1 - y2;
if(z1 < )
{
z1 = -z1;
}
if(z2 < )
{
z2= -z2;
}
return z1 + z2;
}
int main(void)
{
//ios::sync_with_stdio(false);
int n,m,i;
long long ans;
while(~scanf("%d %d",&n,&m))
{
for(i = ;i <= n;i++)
{
scanf("%lld %lld %lld %lld",&z[i].x1,&z[i].y1,&z[i].x2,&z[i].y2);
}
//printf("1111\n");
ans = ;
ans += dis(z[n].x1,z[n].y1,z[n].x2,z[n].y2);
//printf("2222 %lld\n",ans);
for(i = n - ;i >= ;i--)
{
ans += min(dis(z[i].x1,z[i].y1,z[i + ].x1,z[i + ].y1) + dis(z[i].x2,z[i].y2,z[i + ].x2,z[i + ].y2)
,dis(z[i].x1,z[i].y1,z[i + ].x2,z[i + ].y2) + dis(z[i].x2,z[i].y2,z[i + ].x1,z[i + ].y1));
/*printf("%d %lld\n",i,min(dis(z[i].x1,z[i].y1,z[i + 1].x1,z[i + 1].y1) + dis(z[i].x2,z[i].y2,z[i + 1].x2,z[i + 1].y2)
,dis(z[i].x1,z[i].y1,z[i + 1].x2,z[i + 1].y2) + dis(z[i].x2,z[i].y2,z[i + 1].x1,z[i + 1].y1)));*/
}
printf("%lld\n",ans);
}
return ;
}

C.最小边覆盖

Code:kk

Thinking:kk zz

用树形dp找每个联通块 树的直径,树的直径大于等于4的就肯定不行,有孤立的点也不行,就这样。

然而别人都是用结论做的,每条边连上去后,边两边的点只能有一个入度大于1.

我就是个弟弟。

#include<bits/stdc++.h>
#define CLR(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=;
const int inf=0x3f3f3f3f;
int fa[maxn],n,m;
bool vis[maxn];
int head[maxn],tot;
struct edge{
int to,Next;
}a[maxn<<];
void init() {
CLR(vis,);
CLR(head,-),tot=;
}
void addv(int u,int v){
a[++tot].to=v;
a[tot].Next=head[u];
head[u]=tot;
}
int u,v,maxx;
int dfs(int u,int deep,int fa)
{
// printf("u:%d\n",u);
int fmax=,smax=;
vis[fa]=;
for(int i=head[u];i!=-;i=a[i].Next)
{
int v=a[i].to;
if(v==fa)continue;
if(vis[v]==)
{
maxx=inf;
return inf;
}
vis[v]=;
int tep=dfs(v,deep+,u);
if(fmax==)fmax=max(fmax,tep);
else if(smax==){
smax=tep;
if(fmax<smax)swap(fmax,smax);
}
else if(tep>fmax){
smax=fmax,fmax=tep;
}else if(tep>smax){
smax=tep;
}
}
// printf("u:%d\n",u);
// printf("maxx:%d\n",maxx);
// printf("fmax:%d smax:%d\n",fmax,smax);
maxx=max(maxx,max(fmax+smax,fmax+deep));
if(maxx>=inf)return inf; return fmax+;
}
int main() {
while(cin>>n>>m) {
init();
while(m--) {
scanf("%d%d",&u,&v);
addv(u,v),addv(v,u);
}
for(int i=;i<=n;i++)
{
if(vis[i]==)
{
dfs(i,,-);
}
if(maxx>=)
{
break;
}
}
for(int i=;i<=n;i++)
{
if(vis[i]==){
puts("No\n");
return ;
}
}
if(maxx>=){
printf("No\n");
}else{
puts("Yes");
}
}
}

D.欧拉回路

题解待补。

F.小小马

Code:zz

Thinking:zz

马是走日字的,因此走一步后,他所在的格子的颜色和上一格肯定是不一样的,因此,如果他的起点颜色和终点颜色是一样的,那么肯定是No;如果颜色是一样的,那么只要起点和终点是互相可达的,那么是Yes,反之是No。除了3*3的棋盘和2*n的棋盘需要判断是否可达外,其他都能可达。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<math.h>
#include<cmath>
#include<time.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>
#include<numeric>
#include<stack>
#include<bitset>
#include<unordered_map>
const int maxn = 0x3f3f3f3f;
const double EI = 2.71828182845904523536028747135266249775724709369995957496696762772407663035354594571382178525166427;
const double PI = 3.141592653589793238462643383279;
using namespace std;
int main(void)
{
//ios::sync_with_stdio(false);
int n,m,s1,s2,e1,e2;
while(~scanf("%d %d",&n,&m))
{
scanf("%d %d %d %d",&s1,&s2,&e1,&e2);
if(n > m)
{
int r = n;
n = m;
m = r;
}
if(n == && m == )
{
if(s1 == && s2 == || e1 == && e2 == )
{
printf("No\n");
}
else if((s1 + s2) % == (e1 + e2) % )
{
printf("No\n");
}
else
{
printf("Yes\n");
}
}
else if(n == )
{
if(s1 > || e1 > )
{
int r = e1;
e1 = e2;
e2 = r; r = s1;
s1 = s2;
s2 = r;
}
if(e1 == s1)
{
printf("No\n");
}
else
{
if((abs(e2 - s2) - ) % == )
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
else
{
if((s1 + s2) % == (e1 + e2) % )
{
printf("No\n");
}
else
{
printf("Yes\n");
}
}
}
return ;
}

G.置置置换

Code:pai爷

Thinking:pai爷

dp,注意到上凸和下凸的答案是一样的,从下到大枚举插入的数用组合数搞一下方案

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int p=1e9+;
ll dp[],sum[],fac[],inv[];
ll qpow(ll a,ll b)
{
ll ret=;a%=p;
while(b)
{
if(b&) ret=ret*a%p;
b/=;a=a*a%p;
}
return ret;
}
ll C(ll n,ll m)
{
if(m>n) return ;
return 1ll * fac[n] * inv[m] % p * inv[n - m] % p;
} int main()
{
fac[]=;inv[]=;
for(int i=;i<=;i++)
{
fac[i]=1ll*fac[i-]*i%p;
inv[i]=qpow(fac[i],p-);
}
int n;
scanf("%d",&n);
dp[]=dp[]=;
sum[]=;
for(int i=;i<=n;i++)
{
sum[i]=;
for(int j=;j<=i;j++)
{
sum[i]=(sum[i]+dp[j-]*dp[i-j]%p*C(i-,j-)%p) %p;
}
dp[i]=sum[i]*qpow(,p-)%p;
}
printf("%lld\n",dp[n]);
return ;
}

H.咆咆咆哮

Code:pai爷

Thinking:pai爷

一个裸的贪心,计算一下式子枚举保留了k个物品,之后sort一下。取前k个。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
struct node{
int c,id;
}sum[];
int a[],b[];
long long p,q,ans=;
int n;
bool cmp(node a,node b)
{
return a.c>b.c;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
}
for(int k=;k<=n;k++)
{
p=;q=;
for(int i=;i<=n;i++)
{
sum[i].c=a[i]-k*b[i];
sum[i].id=i;
}
sort(sum+,sum++n,cmp);
for(int i=;i<=k;i++)
{
p=p+a[sum[i].id];
}
for(int i=k+;i<=n;i++)
{
q=q+b[sum[i].id];
}
ans=max(ans,p+1ll*q*k);
}
printf("%lld\n",ans);
}

K.两条路径

Code:kk zz

Thinking:kk

选取的两条链交点是x,所以就是选取和x有关的两条大链,而且查询次数非常少,所以就是求每个节点的四条子链的总和,如果子链为负数,则不取。

#include<bits/stdc++.h>
#define CLR(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=;
const int inf=0x3f3f3f3f;
int n,m;
bool vis[maxn];
int head[maxn],tot;
struct edge{
int to,Next;
}a[maxn<<];
ll val[maxn];
ll pre[];
void init() {
CLR(vis,);
CLR(head,-),tot=;
pre[]=;
for(int i=;i<=;i++)
{
pre[i]=pre[i-]*;
}
}
void addv(int u,int v){
a[++tot].to=v;
a[tot].Next=head[u];
head[u]=tot;
}
int u,v;
ll son[maxn][];
ll dfs(int u,int fa)
{
for(int i=head[u];i!=-;i=a[i].Next)
{
int v=a[i].to;
if(v==fa)continue;
ll tep=dfs(v,u);
int flag = ;
for(int j=;j<;j++)
{
if(son[u][j]==){
son[u][j]=tep;
flag = ;
break;
}
}
sort(son[u],son[u]+);
if(son[u][]<tep && flag){
son[u][]=tep;
}
sort(son[u],son[u]+);
}
// printf("u:%d\n",u);
return max((ll),son[u][]+val[u]);
}
int main() {
while(cin>>n) {
init();
for(int i=;i<=n;i++)
{
scanf("%d",&u);
if(u>=)
{
val[i]=pre[u];
}else{
val[i]=-pre[-u];
}
} for(int i=;i<n;i++)
{
scanf("%d%d",&u,&v);
addv(u,v),addv(v,u);
}
int q;
cin>>q;
while(q--)
{
memset(son,,sizeof(son));
scanf("%d",&u);
dfs(u,-);
ll ans=val[u];
for(int i=;i<;i++)
{
ans+=max((ll),son[u][i]);
//printf("%lld ",son[u][i]);
}
//printf("\n");
//printf("%lld\n",ans);
int op= (ans<);
if(ans < )
{
ans = -ans;
}
int cc[],cnt = ;
while(ans)
{
cc[cnt++] = ans %;
ans /= ;
}
if(op)
{
printf("-");
}
if(cnt == )
{
printf("");
}
for(int i = cnt - ;i >= ;i--)
{
printf("%d",cc[i]);
}
printf("\n");
} }
}

赛后总结:

kk:今天有蛮多图的题目的,但是读c题的题意没读懂,别人用简单结论一小时不到就做出的题目,我写了树形dp求树的直径两小时后才ac,k题也是个树形dp的题,套了上一题的代码,结果int忘记改成long long了,wawawawawa,贼菜,把队友的腿都给抱断了。

pai爷:今天状态很差,那道DP题一直在想DP[i][j]表示枚举到第i个位置填了j的方案数,但是无法满足排列,想了很久才写出来,之后那道欧拉回路的时间不多了,找规律的题还是缺少一个系统的操作,最后时刻还是没有写出来。

zz:今天很快写掉了两个签到题,然后帮队友看c题,看了很久没看出来,后来发现题读错了,然后又一起看了k,做法很快就出了,代码打出来以后要出了很多bug,wa了很多次,改了很久才过,写代码还是要仔细点,不然小bug改到死。

05-11 21:43