@[yjjr](/user/5088) 是不是洛谷不支持我这里的输入方式? 因为我原先遇到过因为洛谷不支持getchar读入字符导致全部wa
by 影法师 @ 2020-01-02 10:13:33
确实不支持
by exorcist @ 2020-01-02 10:59:35
请问是哪一道题
by exorcist @ 2020-01-02 11:00:16
@[exorcist](/user/266812) P3261 [JLOI2015]城池攻占
后面我发现是有一些long long的入参，结果写成了int，改了一发
```cpp
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
//#define LOCAL
const int maxn = 3e5+5;
int n,m, head[maxn], cnt;
struct LeafHeapNode // 其实就是m个骑士的数据结构
{
int lc, rc, npl, win, c;
ll val, addtag, multag;
LeafHeapNode():multag(1ll){}
}lh[maxn];
ll kk(int x)
{
return lh[x].val * lh[x].multag + lh[x].addtag; // 先做乘法再做加法
}
void kz(int x, ll addtag, ll multag) // (x*a+b)*multag+addtag= x*a*multag + b*multag+addtag, 其中(a,b)是lh[x]既存的加法tag和乘法tag
{
if (!x)
{
return;
}
lh[x].multag *= multag;
lh[x].addtag *= multag;
lh[x].addtag += addtag;
}
void pushdown(int x) // 下推lh[x]加法tag和乘法tag
{
if (!x)
{
return;
}
int lc = lh[x].lc;
int rc = lh[x].rc;
ll addtag = lh[x].addtag;
ll multag = lh[x].multag;
kz(lc, addtag, multag);
kz(rc, addtag, multag); // 下推tag
lh[x].val = kk(x); // 算账
lh[x].addtag = 0;
lh[x].multag = 1ll; // 恢复
}
int merge(int x,int y)
{
if (!x || !y)
{
return x + y;
}
if (kk(x) > kk(y))
{
swap(x,y);
}
pushdown(x);
lh[x].rc = merge(lh[x].rc, y);
if (lh[lh[x].rc].npl > lh[lh[x].lc].npl)
{
swap(lh[x].lc, lh[x].rc);
}
lh[x].npl = lh[lh[x].rc].npl + 1;
return x;
}
struct City
{
int hid, dep, die, a; // hid是此座城市对应的骑士团(即活着从此座城市走出去的骑士团体)对应的左式堆的堆顶骑士的编号(1~m), dep是作为树的节点的深度
ll h, v;
} cs[maxn];
struct Arc
{
int from, to, nxt;
} g[maxn];
void addarc(int from,int to)
{
g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from];
head[from] = cnt++;
}
void dfs(int cur)
{
for (int h = head[cur], to; ~h; h = g[h].nxt)
{
to = g[h].to;
cs[to].dep = cs[cur].dep + 1;
dfs(to);
}
}
void printt(int cur)
{
if (!cur)
{
return;
}
printf("%d ", cur);
int lc = lh[cur].lc;
printt(lc);
int rc = lh[cur].rc;
printt(rc);
}
int getwin(int ed, int x) // 计算x号骑士攻下的城市数量
{
int st = lh[x].c; // x号骑士出发的城市, ed是该骑士死亡的城市
return cs[st].dep - cs[ed].dep;
}
void dfs1(int cur)
{
int h, to, hid ,lc, rc;
for (h = head[cur], to; ~h; h = g[h].nxt)
{
to = g[h].to;
dfs1(to); // 应该先解决子问题, 得到to这座城市对应的骑士团的hid
cs[cur].hid = merge(cs[cur].hid, cs[to].hid);
} // 第一步. 集结骑士团
h = cs[cur].h, hid = cs[cur].hid, lc, rc;
if (!hid) // 该城市没有骑士团
{
return;
}
if (cur == 3891)
{
//puts("");
//printt(hid);
}
while(kk(hid) < h) // 则需要将lh[hid] pop掉, 即骑士 hid 牺牲掉了
{
++cs[cur].die; // hid号骑士牺牲在cur这座城市, 维护答案, 即在此城市牺牲的骑士数量
lh[hid].win = getwin(cur, hid); // 维护答案, 即hid号骑士攻陷的城市数量
lc = lh[hid].lc;
rc = lh[hid].rc;
pushdown(hid);
hid = cs[cur].hid = merge(lc, rc);
if (!hid) // 骑士团全军覆没
{
return;
}
} // 第二步. 模拟打仗
if (cs[cur].a)
{
lh[hid].multag *= cs[cur].v;
lh[hid].addtag *= cs[cur].v;
}
else
{
lh[hid].addtag += cs[cur].v;
} // 第三步. 清算tag
}
void dfs2(int cur)
{
if (!cur)
{
return;
}
lh[cur].win = cs[lh[cur].c].dep;
dfs2(lh[cur].lc);
dfs2(lh[cur].rc);
}
int main()
{
#ifdef LOCAL
freopen("d:\\data.in","r",stdin);
freopen("d:\\my.out", "w", stdout);
#endif
lh[0].npl = -1;
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &cs[i].h);
}
for (int i = 2, fa; i<=n; i++)
{
scanf("%d%d%lld", &fa, &cs[i].a, &cs[i].v);
addarc(fa, i);
}
cs[1].dep = 1;
dfs(1); // 预处理出每个树节点（即城市）的深度
for (int i = 1; i<=m; i++)
{
scanf("%lld%d", &lh[i].val, &lh[i].c); // 第i位骑士从城市c出发
cs[lh[i].c].hid = merge(cs[lh[i].c].hid, i); // 维护每座城市的骑士团对应的堆的id
}
dfs1(1);
dfs2(cs[1].hid); // 统计最后打通关的骑士
for (int i = 1; i<=n; i++)
{
printf("%d\n", cs[i].die);
}
for (int i = 1; i<=m; i++)
{
printf("%d\n", lh[i].win);
}
return 0;
}
```
但是还是全部wa掉~ 跪求大佬指点！
by 影法师 @ 2020-01-02 12:04:45
造数据的代码如下
```cpp
#include "stdafx.h"
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include<random>
#include <map>
using namespace std;
const int inf = 0x3f3f3f3f;
typedef long long ll;
typedef vector<int>::iterator vit;
#define SWAP(x,y) x^=y^=x^=y
typedef pair<int,int> P;
const int maxn = 10000;
map<int,int> mp;
bool v[200005];
int tot, num, fa[maxn];
void dfs(int cur, int dep) // 随机生成树型数据的代码
{
if (dep >= 17)
{
return;
}
int chnum = rand()%1+3;
for (int i = 1; i<=chnum; i++)
{
++tot;
fa[tot] = cur;
dfs(tot, dep+1);
}
}
int main()
{
freopen("d:\\data.in", "w", stdout);
srand((int)(time(0)));
int n,m;
dfs(++tot, 1);
n = tot;
m = rand();
printf("%d %d\n", n, m);
for (int i = 1; i<=n; i++)
{
printf("%d ", rand()*(10007)- (10003)* rand());
}
puts("");
for (int i = 2, a, v;i<=n; i++)
{
a = rand()%2;
if (a)
{
v = rand()%1000;
}
else
{
v = rand()*(10007)- (10003)* rand();
}
printf("%d %d %d\n", fa[i], a, v);
}
puts("");
for (int i = 1; i<=m; i++)
{
printf("%d %d\n", rand()*(10007)- (10003)* rand(), rand()%n+1);
}
fclose(stdout);
return 0;
}
```
by 影法师 @ 2020-01-02 12:07:17
兄弟，你加一下我q
by exorcist @ 2020-01-02 12:18:42
2486816414
by exorcist @ 2020-01-02 12:18:57
吧
by exorcist @ 2020-01-02 12:19:12
发现了群友
by hly1204 @ 2020-01-02 13:02:50
@[exorcist](/user/266812) 好的, 已经发送申请好友了，麻烦通过一下，谢谢
by 影法师 @ 2020-01-02 13:05:21