HDU 2020 多校第四场 游记

这次 1006 挂了 5 发,太惨了 /ll,罚时罚到了 rk7……

1001

毒瘤三维计算几何,不看不看

1002

签到题,显然每个武器打死对方所用的时间都能算出来,

O(n2)O(n^2)

O(n2) 枚举即可。

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

const int MAXN = 1005;
int aa[MAXN], dd[MAXN], ta[MAXN], T, n;

int main() {
for (scanf("%d", &T); T--;) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", aa + i, dd + i);
for (int i = 1; i <= n; i++)
ta[i] = 99 / aa[i] * dd[i];
double mx = 0;
for (int i = 1; i <= n; i++) {
int sum = 0;
for (int j = 1; j <= n; j++)
sum += ta[i] == ta[j] ? 1 : (ta[i] < ta[j] ? 2 : 0);
mx = max(mx, 0.5 * sum / n);
}
printf("%.9lf\n", mx);
}
return 0;
}

1003

正解还没看,场上写的是乱搞做法。

考虑把两个班的人合在一起 random_shuffle,这个时候我们 dp 第二维(即一班的力量和减二班的力量和)不会很大,我们取大概 50000 足够了,于是直接

O(50000n)O(50000n)

O(50000n) dp 即可。

code by lqs

#include<bits/stdc++.h>
using namespace std;
const int maxw=50000,all=100000;
int test,n,m,w[2222],v[2222],la,nw,id[2222];
long long dp[222222];
void chkmax(long long &x,long long y)
{
if (x<y) x=y;
}
int main()
{
scanf("%d",&test);
srand(time(0));
while(test--)
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d%d",&w[i],&v[i]);
}
for (int i=1;i<=m;i++)
{
scanf("%d%d",&w[i+n],&v[i+n]);
}
for (int i=0;i<=2*maxw;i++) dp[i]=-1e18;
dp[maxw]=0;
for (int i=1;i<=n+m;i++) id[i]=i;
random_shuffle(id+1,id+n+m+1);
for (int i=1;i<=n+m;i++)
{
if (id[i]<=n)
{
for (int j=all-w[id[i]];j>=0;j--)
{
chkmax(dp[j+w[id[i]]],dp[j]+v[id[i]]);
}
}
else
{
for (int j=w[id[i]];j<=all;j++)
{
chkmax(dp[j-w[id[i]]],dp[j]+v[id[i]]);
}
}
}
printf("%lld\n",dp[maxw]);
}
return 0;
}

1004

最短路裸题,每个点拆成两个点分别表示经过之后是左手还是右手拿着蛋糕,直接 dijkstra 即可。复杂度

O(nlogn)O(n \log n)

O(nlogn)。

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

const int MAXN = 200005;
struct Edge { int v, w; };
struct Node {
LL d; int u, t;
bool operator<(const Node &n) const { return d > n.d; }
};
vector<Edge> edge[MAXN];
LL dis[MAXN][2];
int T, n, m, s, t, x;
char str[MAXN];
priority_queue<Node> pq;

int main() {
for (scanf("%d", &T); T--;) {
scanf("%d%d%d%d%d", &n, &m, &s, &t, &x);
scanf("%s", str + 1);
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
edge[u].push_back(Edge { v, w });
edge[v].push_back(Edge { u, w });
}
for (int i = 1; i <= n; i++) dis[i][0] = dis[i][1] = 1e18;
if (str[s] != 'R') pq.push(Node { dis[s][0] = 0, s, 0 });
if (str[s] != 'L') pq.push(Node { dis[s][1] = 0, s, 1 });
while (!pq.empty()) {
Node d = pq.top(); pq.pop();
if (dis[d.u][d.t] < d.d) continue;
if (d.u == t) break;
for (const Edge &e : edge[d.u]) {
LL w = e.w + d.d;
int t = str[e.v] == 'R' ? 1 : (str[e.v] == 'L' ? 0 : d.t);
if (t == d.t && w < dis[e.v][t])
pq.push(Node { dis[e.v][t] = w, e.v, t });
w += x;
if (str[e.v] == 'M') t = !t;
if (t != d.t && w < dis[e.v][t])
pq.push(Node { dis[e.v][t] = w, e.v, t });
}
}
printf("%lld\n", min(dis[t][0], dis[t][1]));
while (!pq.empty()) pq.pop();
for (int i = 1; i <= n; i++) edge[i].clear();
}
return 0;
}

1005

比较签到的题,不难发现如果一个序列相邻元素两两不同,那么方案数就是斐波那契数列(可以枚举最后一个是否和倒数第二个交换,分别对应

n1,n2n-1,n-2

n−1,n−2 的状态)。

所以我们把一个序列划分成若干个极长的相邻元素两两不同的段,答案就是这些段对应斐波那契数的乘积。复杂度

O(n)O(n)

O(n)。(比如 1,2,3,3,3,4,4 可以划分成 1,2,3 | 3 | 3,4 | 4)

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

const int MAXN = 200005, MOD = 1e9 + 7;
LL f[MAXN];
int T, n;
string aa[MAXN];
char str[MAXN];

int main() {
f[0] = 1, f[1] = 1;
for (int i = 2; i <= 1e5; i++)
f[i] = (f[i - 1] + f[i - 2]) % MOD;
for (scanf("%d", &T); T--;) {
scanf("%d", &n);
int cnt = 0;
LL ans = 1;
for (int i = 1; i <= n; i++) {
scanf("%s", str);
aa[i] = str;
if (aa[i] != aa[i - 1]) ++cnt;
else ans = ans * f[cnt] % MOD, cnt = 1;
}
ans = ans * f[cnt] % MOD;
printf("%lld\n", ans);
}
return 0;
}

1006

计算几何题,因为环交写错了被卡了很久……

二分答案,每个分针都有一个限制,即最终分针必须属于某段弧,时针同理。

于是我们就要求弧的交,断环为链,端点离散化,这样对于分针弧的限制,我们进行区间加操作。那么最终如果一个点属于弧交,那么它的值必然为分针个数。时针同理。

接下来就是判断是否存在一个合法的时间,使得时针、分针分别满足他们的限制。我们枚举小时数,然后枚举分针所在的区间,这样就得到了时针的合法区间,看看这个区间里是否有满足要求的时针即可。

上述过程都可以差分、前缀和、two pointers 优化成线性(但是还有个离散化需要排序),复杂度

O((12n+nlogn)log109)O((12 n + n \log n) \log 10^9)

O((12n+nlogn)log109)。

code by lqs

#include<bits/stdc++.h>
using namespace std;
int test;
int n,h,m,s,cnt,cpt,rg;
pair<double,double> p[55555];
pair<double,int> arr[222222];
double l,r,mid,del;
double ls,rs,ll1,rr1,lp1,rp1,ll2,rr2,lp2,rp2;
double l11,r11,l12,r12,l21,r21,l22,r22,lt,rt;
pair<double,double> v1[222222],v2[222222];
int cnt1,cnt2;
bool check()
{
cnt=0;cpt=0;cnt1=cnt2=0;
arr[++cnt]=make_pair(0.00,1);
arr[++cnt]=make_pair(360.00,-1);
for (int j=1;j<=n;j++)
{
ls=p[j].first-mid;
rs=p[j].first+mid;
if (ls<0.00)
{
cpt++;
arr[++cnt]=make_pair(rs,-1);
arr[++cnt]=make_pair(ls+360.00,1);
}
else if (rs>360.00)
{
cpt++;
arr[++cnt]=make_pair(rs-360.00,-1);
arr[++cnt]=make_pair(ls,1);
}
else
{
arr[++cnt]=make_pair(ls,1);
arr[++cnt]=make_pair(rs,-1);
}
}
sort(arr+1,arr+cnt+1);
for (int i=1;i<cnt;i++)
{
cpt+=arr[i].second;
if (cpt==n+1)
{
v1[++cnt1]=make_pair(arr[i].first,arr[i+1].first);
}
}
cnt=cpt=0;
arr[++cnt]=make_pair(0.00,1);
arr[++cnt]=make_pair(360.00,-1);
for (int j=1;j<=n;j++)
{
ls=p[j].second-mid;
rs=p[j].second+mid;
if (ls<0.00)
{
cpt++;
arr[++cnt]=make_pair(rs,-1);
arr[++cnt]=make_pair(ls+360.00,1);
}
else if (rs>360.00)
{
cpt++;
arr[++cnt]=make_pair(rs-360.00,-1);
arr[++cnt]=make_pair(ls,1);
}
else
{
arr[++cnt]=make_pair(ls,1);
arr[++cnt]=make_pair(rs,-1);
}
}
sort(arr+1,arr+cnt+1);
for (int i=1;i<cnt;i++)
{
cpt+=arr[i].second;
if (cpt==n+1)
{
v2[++cnt2]=make_pair(arr[i].first,arr[i+1].first);
}
}
for (int i=0;i<12;i++)
{
del=(double)i*30.00;
rg=1;
for (int j=1;j<=cnt1;j++)
{
while(rg<=cnt2)
{
lt=del+(v2[rg].first/12.00);rt=del+(v2[rg].second/12.00);
if (lt>v1[j].second) break;
else if (rt<v1[j].first);
else return 1;
rg++;
}
}
}
return 0;
}
int main()
{
scanf("%d",&test);
while(test--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d:%d:%d",&h,&m,&s);
if (h>=12) h-=12;
p[i]=make_pair((double)h*30.00+(double)(m*60+s)/120.00,(double)(m*60+s)/10.00);
}
l=0;r=180.00;
for (int i=1;i<=50;i++)
{
mid=(l+r)/2.00;
if (check()) r=mid;
else l=mid;
}
printf("%.9lf\n",l);
}
return 0;
}

1007

难得一见凉心的

10510^5

105 网络流题(难道正解不是网络流?)。

考虑每个监测点

xi,tix_i,t_i

xi​,ti​ 实际上是在限制什么。这就等价于在

00

0 时刻存在一个向右跑的在

xitix_i-t_i

xi​−ti​ 的学生、或者一个向左跑的在

xi+tix_i+t_i

xi​+ti​ 的学生。

我们把向左跑、向右跑的学生分别放在二分图的两边,然后对于每个监测点,就把上述涉及到的两个学生连一条边,最后是要求这个二分图的最小点覆盖。众所周知二分图最小点覆盖等于最大匹配,直接 dinic 即可,dinic 跑二分图匹配的复杂度是

O(mn)O(m \sqrt n)

O(mn​) 的,可以接受。

code by lqs

#include<bits/stdc++.h>
using namespace std;
const int md=993217,inf=1e9;
int test,n,m,s,t,head[666666],nxt[666666],to[666666],cap[666666],xx[111111],tt[111111],cnt,cur[222222],dist[222222];
struct ht
{
int head[md+5],nxt[222222],val[222222],cnt;
void clear()
{
for (int i=1;i<=cnt;i++) head[(val[i]%md+md)%md]=0;
for (int i=1;i<=cnt;i++) nxt[i]=val[i]=0;
cnt=0;
}
void add(int x)
{
int g=(x%md+md)%md;
for (int i=head[g];i;i=nxt[i])
{
if (val[i]==x) return;
}
++cnt;val[cnt]=x;nxt[cnt]=head[g];
head[g]=cnt;
}
int find(int x)
{
int g=(x%md+md)%md;
for (int i=head[g];i;i=nxt[i])
{
if (val[i]==x) return i;
}
return 0;
}
}ht1,ht2;
void addedge(int s,int t,int cp)
{
cnt++;
nxt[cnt]=head[s];head[s]=cnt;
to[cnt]=t;cap[cnt]=cp;
cnt++;
nxt[cnt]=head[t];head[t]=cnt;
to[cnt]=s;cap[cnt]=0;
}
void bfs(int s)
{
memset(dist,-1,sizeof(dist));
queue<int> q;
q.push(s);
dist[s]=0;
while(!q.empty())
{
int x=q.front();q.pop();
for (int i=head[x];i;i=nxt[i])
{
if (!cap[i]) continue;
if (!~dist[to[i]])
{
dist[to[i]]=dist[x]+1;
q.push(to[i]);
}
}
}
}
int dfs(int i,int f,int t)
{
if (i==t) return f;
int tmp=f;
for (int &j=cur[i];j;j=nxt[j])
{
if (!cap[j] || dist[to[j]]!=dist[i]+1) continue;
int d=dfs(to[j],min(cap[j],tmp),t);
if (d)
{
cap[j]-=d;
cap[j^1]+=d;
tmp-=d;
if (!tmp) break;
}
else dist[to[j]]=0;
}
return f-tmp;
}
int dinic()
{
int res=0;
while(1)
{
for (int i=1;i<=t;i++) cur[i]=head[i];
bfs(s);
if (!~dist[t]) break;
res+=dfs(s,inf,t);
}
return res;
}
int main()
{
scanf("%d",&test);
while(test--)
{
scanf("%d",&n);ht1.clear();ht2.clear();
for (int i=1;i<=n;i++)
{
scanf("%d%d",&xx[i],&tt[i]);
ht1.add(xx[i]-tt[i]);
ht2.add(xx[i]+tt[i]);
}
s=ht1.cnt+ht2.cnt+1;t=s+1;
cnt=1;
for (int i=1;i<=n;i++)
{
addedge(ht1.find(xx[i]-tt[i]),ht1.cnt+ht2.find(xx[i]+tt[i]),1);
}
for (int i=1;i<=ht1.cnt;i++) addedge(s,i,1);
for (int i=1;i<=ht2.cnt;i++) addedge(ht1.cnt+i,t,1);
printf("%d\n",dinic());
for (int i=1;i<=t;i++) head[i]=0;
for (int i=1;i<=cnt;i++)
{
nxt[i]=cap[i]=to[i]=0;
}
cnt=1;
}
return 0;
}

1008

乱搞爆搜题,听说可以 random_shuffle 有用边爆搜生成树来判,期望个数不会很多。

1009

套路题,把贡献拆到每条边上。假设一条边的两边分别选了

i,mii,m-i

i,m−i 个点,那么它的贡献就是

min(i,mi)\min(i,m-i)

min(i,m−i)。

于是对于一条边,假设它两边的树大小分别为

s,nss,n-s

s,n−s,那么它的贡献就是这个:

i=0m(si)(nsmi)min(i,mi)\sum_{i=0}^m\binom{s}{i}\binom{n-s}{m-i}\min(i,m-i)

i=0∑m​(is​)(m−in−s​)min(i,m−i)

拆一下组合数,变成:

s!(ns)!i=0mmin(i,mi)i!(si)!(mi)!(nsm+i)!s!(n-s)!\sum_{i=0}^m\frac{\min(i,m-i)}{i!(s-i)!(m-i)!(n-s-m+i)!}

s!(n−s)!i=0∑m​i!(s−i)!(m−i)!(n−s−m+i)!min(i,m−i)​

由于

n,mn,m

n,m 都是固定的,那么右边变成了一个只和

i,sii,s-i

i,s−i 有关的式子,显然是个卷积的形式。那么就变成了一个

mm

m 次多项式和

nmn-m

n−m 次多项式卷起来,复杂度

O(nlogn)O(n \log n)

O(nlogn),可以通过了。

1010

1011

坑爹题,刚开始在解高阶微分方程,后来 djq 发现由于

GG

G 太小,直接输出距离即可……

#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MOD = 998244353;

int main()
{
int T, a, b, d, t;
scanf("%d", &T);
while(T --) {
scanf("%d%d%d%d", &a, &b, &d, &t);
printf("%d\n", d);
}
return 0;
}

1012

我们考虑如下的矩阵:

3, 5, 4, 2, 1
2, 1, 3, 5, 4
5, 4, 2, 1, 3
1, 3, 5, 4, 2
4, 2, 1, 3, 5

会发现每个格子及其上下左右的格子,恰好是 5 的排列,并且这个矩阵可以无限循环摆放,都满足这个性质。

于是我们抠出一个原点

(x,y)(x,y)

(x,y) 及到它曼哈顿距离

k\le k

≤k 的所有点(

kk

k 可以尝试着取),按顺序把能染色的

11

1 全染色,然后把能染色的

22

2 全染色……以此类推。不难发现,如果上述矩阵无穷大的话,第

ii

i 步就相当于能够把所有

i5i-5

i−5 的格子变成

ii

i。

但是现在矩阵并不能无穷大,于是我们尝试着设上面所说的最大距离

kk

k,然后依次把能染色的进行染色。

k=72k=72

k=72 的时候,能够取到

100100

100 这个数字,大约七万次操作(事实上可以先 bfs,算出每个位置需要染到几就可以停止了,这样会大幅度减少操作次数)。

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

const int MAXN = 205, dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };
const int mp[5][5] = {
3, 5, 4, 2, 1,
2, 1, 3, 5, 4,
5, 4, 2, 1, 3,
1, 3, 5, 4, 2,
4, 2, 1, 3, 5,
};
const int B = 144;
int col[MAXN][MAXN];

bool check(int x, int y) {
int p = col[x][y], t = 0;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx > B || ny < 0 || ny > B) continue;
if (col[nx][ny] < col[x][y] && col[nx][ny] + 4 >= col[x][y])
t |= 1 << (col[x][y] - col[nx][ny]);
}
return __builtin_popcount(t) == min(p - 1, 4);
}

void push(int x, int y, int c) {
printf("%d %d %d\n", x, y, c);
}

int dis(int x, int y, int a, int b) {
return abs(x - a) + abs(y - b);
}

int main() {
int x = B / 2, y = B / 2, n;
scanf("%d", &n);
for (int i = 0; i <= B; i++)
for (int j = 0; j <= B; j++) {
if (dis(i, j, x, y) <= B / 2)
col[i][j] = mp[i % 5][j % 5];
else col[i][j] = -1e9;
}
for (int i = 1; i <= n; i++)
for (int a = 0; a <= B; a++)
for (int b = 0; b <= B; b++) if (col[a][b] > -1e9 && col[a][b] % 5 == i % 5 && dis(a, b, x, y) <= B / 2) {
col[a][b] = i;
if (check(a, b)) push(a, b, i);
else col[a][b] = -1e9;
}
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

HDU 2020 多校第四场 游记

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » HDU 2020 多校第四场 游记
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏