题面：CF1179D
给一棵
个点的树，求加入一条边后，最多有多少条无向简单路径。
简单路径定义为任意一个点最多经过一次的路径。
直接求直径的解法正确性极高，如何证明其正确性或证伪
分类：训练记录
完整快读快输模板（使用范例见main函数）
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
using namespace std;
#define getchar() (S==T&&(T=(S=A)+fread(A,1,1<<15,stdin),S==T))?EOF:*S++
char A[1<<15],*S,*T;
void read() {}
template<typename T1,typename ...T2>
void read(T1&num,T2&...rest)
{
num=0;
char c;
bool f=0;
while(!isdigit(c=getchar()))
f=c=='-';
do
num=num*10+c-'0';
while(isdigit(c=getchar()));
if(f)
num=-num;
read(rest...);
}
template<typename T>
void write(T num)
{
if(num<0)
putchar('-'),num=-num;
if(num>9)
write(num/10);
putchar(num%10+'0');
}
template<const char ch=' '>void write() {}
template<const char ch=' ',typename T,typename ...arr>
void write(T num,arr... rest)
{
write(num);
if(ch!=-1)
putchar(ch);
write<ch>(rest...);
}
int a,b,c,d;
int main()
{
ios::sync_with_stdio(0);
read(a,b,c,d); //sample input
write<'\n'>(114514,1919810);//sample output
write<' '>(1919810,114514)//sample output 2
return 0;
}
赛前冲刺套题day3
明天考试，很慌……
CSP-S2021加油！
[题目1]绿洲
这题真·卡常数到极致......
其实这题也没有那么难，就是做K遍最短路
因为边权为1，所以最短路算法应选择bfs()（没想到吧）
另几个最短路算法(dijkstra(未知),dijkstra堆优化(80分),spfa(90分)……)均不能满分(开O3+快读卡常数除外)
所以我选择了卡常数……
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
int n,m,k;
int city[100005],final_dist[100005];
int h[100005],e[200005],ne[200005],idx;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra(int S)//本人之前写的是dij堆优化,懒得把函数名改成spfa了
{
int dist[100005],st[100005]={0};
memset(dist, 0x3f, sizeof dist);
dist[S] = 0;
queue<int> q;
q.push(S);
st[S] = true;
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + 1)
{
dist[j] = dist[t] + 1;
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
for(int i=1;i<=n;i++)final_dist[i]=max(final_dist[i],dist[i]);
}
int main()
{
freopen("oasis.in","r",stdin);
freopen("oasis.out","w",stdout);
memset(h,-1,sizeof h);
n=read();
m=read();
k=read();
for(int i=1;i<=k;i++)city[i]=read();
while(m--)
{
int a=read();
int b=read();
add(a,b);
add(b,a);
}
for(int i=1;i<=k;i++)dijkstra(city[i]);
for(int i=1;i<=n;i++)printf("%d ",final_dist[i]);
return 0;
}
[题目2]数列
vector NB!!!
而且题解说要用并查集维护其实也是不用的
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n;
vector<int>A;
vector<int>pos[10005];
int main()
{
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
A.emplace_back(x);
}
A.emplace_back(0);
int cnt=0,flag=1;
for(int i=0;i<A.size();i++)
{
if(A[i])
{
pos[A[i]].emplace_back(i);
flag=0;
}
else
{
if(!flag)cnt++;
flag=1;
}
}
int res=cnt;
for(int i=0;i<=10000;i++)
{
for(auto item:pos[i])
{
if(A[item-1]&&A[item+1])cnt++;
else if(!A[item-1]&&!A[item+1])cnt--;
A[item]=0;
}
res=max(res,cnt);
}
printf("%d",res);
return 0;
}
[题目3]遛狗
前置知识:P5490 【模板】扫描线
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+10;
typedef long long LL;
int n,cnt=0;
LL x1,x2,y1,y2,X[N<<1];
struct scan
{
LL l,r,h;
int mark;
bool operator < (const scan &P)const
{
return h<P.h;
}
}line[N<<1];
struct tree
{
int l,r,sum;
LL len;
}tr[N<<2];
void build(int k,int l,int r)
{
tr[k]={l,r,0,0};
if(l==r)return;
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void pushup(int x)
{
int l=tr[x].l;
int r=tr[x].r;
if(tr[x].sum)tr[x].len=X[r+1]-X[l];
else tr[x].len=tr[x<<1].len+tr[x<<1|1].len;
}
void modify(int x,LL L,LL R,int c)
{
int l=tr[x].l;
int r=tr[x].r;
if(X[r+1]<=L||R<=X[l])return;
if(L<=X[l]&&X[r+1]<=R)
{
tr[x].sum+=c;
pushup(x);
return;
}
modify(x<<1,L,R,c);
modify(x<<1|1,L,R,c);
pushup(x);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
X[2*i-1]=x1;
X[2*i]=x2;
line[2*i-1]={x1,x2,y1,1};
line[2*i]={x1,x2,y2,-1};
}
n<<=1;
sort(line+1,line+n+1);
sort(X+1,X+n+1);
int tot=unique(X+1,X+n+1)-X-1;
build(1,1,tot-1);
LL ans=0;
for(int i=1;i<n;i++)
{
modify(1,line[i].l,line[i].r,line[i].mark);
ans+=tr[1].len*(line[i+1].h-line[i].h);
}
printf("%lld",ans);
return 0;
}
然后就没有然后了……
[题目4]食材运输
说是都是暴力，但我要二分[doge]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110,M=15,INF=1<<29;
typedef long long LL;
typedef pair<int,int>PII;
int n,m,k,idx,h[N],d[N][M],g[N][M];
struct Edge
{
int e,ne,w;
}edge[N*2];
void add(int u,int v,int w)
{
edge[++idx]={v,h[u],w};
h[u]=idx;
}
PII dfs(int u,int father,int op)
{
PII res={0,-1};
if(g[u][op])res.second=0;
for(int i=h[u];i;i=edge[i].ne)
{
int to=edge[i].e;
int w=edge[i].w;
if(to==father)continue;
auto t=dfs(to,u,op);
if(t.second!=-1)
{
res.first+=t.first+(w*2);
res.second=max(res.second,t.second+w);
}
}
return res;
}
int state[N],f[1<<M];
bool check(int mid)
{
memset(state,0,sizeof state);
for(int i=1;i<=n;i++)
{
for(int j=0;j<k;j++)
{
if(d[i][j]<=mid)state[i]|=(1<<j);
}
}
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<(1<<k);j++)f[j|state[i]]=min(f[j|state[i]],f[j]+1);
}
return f[(1<<k)-1]<=m;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
for(int j=0;j<k;j++)scanf("%d",&g[i][j]);
}
for(int i=1;i<n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<k;j++)
{
auto t=dfs(i,-1,j);
if(t.second!=-1)d[i][j]=t.first-t.second;
}
}
int l=0,r=INF;
while(l<r)
{
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%d",r);
return 0;
}
最后
CSP-S 2021 加油!
CSP-S 2021 加油!
CSP-S 2021 加油!
赛前冲刺套题day2（还剩下1天练习时间）
我没了，我没了，我真的没了
又是《简单》的一套题。
[题目一]成绩
枚举，但细节非常的多。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,dot;
char s[200010];
void Cout(int start,int end)
{
for(int i=start;i<=end;i++)printf("%c",s[i]);
exit(0);
}
void solve(int i)
{
while(i>=0&&s[i]=='9')s[i--]='0';
if(i==-1)
{
printf("1");
Cout(0,dot-1);
return;
}
s[i]++;
Cout(0,dot-1);
}
int main()
{
freopen("grade.in","r",stdin);
freopen("grade.out","w",stdout);
scanf("%d%d%s",&n,&m,s);
if(!m)Cout(0,n-1);
for(int i=0;i<n;i++)
{
if(s[i]=='.')
{
dot=i;
break;
}
}
for(int i=dot+1;i<n;i++)
{
if(s[i]>='5')
{
if(i==dot+1)solve(dot-1);
else
{
int j=i-1;
s[j]++;
int t=1;
while(t+1<=m&&j!=dot&&s[j]=='5')
{
t++;
s[--j]++;
}
if(j==dot)solve(dot-1);
Cout(0,j);
}
}
}
Cout(0,n-1);
return 0;
}
[第二题]数三角形
数学题，求组合数，用总的方案数-三个点构成直线平行于横轴-三个点构成直线平行于竖轴-三个点构成直线的其他情况
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
long long n,m;
long long ans=0;
long long C(long long x)
{
return x*(x-1)*(x-2)/6;
}
int main()
{
freopen("tri.in","r",stdin);
freopen("tri.out","w",stdout);
scanf("%lld%lld",&n,&m);
n++;
m++;
ans=C(n*m)-m*C(n)-n*C(m);
for(long long i=1;i<n;i++)
{
for(long long j=1;j<m;j++)ans-=2*(n-i)*(m-j)*(__gcd(i,j)-1);
}
printf("%lld",ans);
return 0;
}
[第三题]苹果
万万没有想到，这题竟是一个测试运气的题目
每次从a[]中随机出两个不同下标的数，对他们求gcd()，并把他们的求得gcd的结果分解因数并存到一个数组里(这个步骤多重复几次，多了正确性大，但是不要太大，会导致时间超限),后面就是从大的->小的因数去试一试a[]中的数是否有半数可以整除这个因数，找到就输出并break。
另：二分只有5~10分(有可能是本人二分出错了......)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
const long long N=200005;
long long n;
long long a[N];
vector<long long>divers;
void F(long long x)
{
for(long long i=1;i<=x/i;i++)
{
if(x%i==0)
{
divers.push_back(i);
if(i!=x/i)divers.push_back(x/i);
}
}
}
int main()
{
freopen("apple.in","r",stdin);
freopen("apple.out","w",stdout);
srand(time(0));
scanf("%lld",&n);
for(long long i=1;i<=n;i++)scanf("%lld",&a[i]);
long long T=39;
while(T--)
{
long long xb1=rand()%n+1;
long long xb2=rand()%n+1;
while(xb1==xb2)
{
xb1=rand()%n+1;
xb2=rand()%n+1;
}
F(__gcd(a[xb1],a[xb2]));
}
sort(divers.begin(),divers.end());
divers.erase(unique(divers.begin(),divers.end()),divers.end());
for(long long i=divers.size()-1;i>=0;i--)
{
long long ans=0;
for(long long j=1;j<=n;j++)
{
if(a[j]%divers[i]==0)ans++;
}
if(ans*2>=n)
{
printf("%lld",divers[i]);
return 0;
}
}
printf("1");
return 0;
}
永远不会的第四题........
CSP-S考前冲刺DAY1
今天第一天集训，虽然难度不算难，但出现了亿些些不会写的东西。
[题目1]线段树
正如这道题的名字一样，正解就是线段树，只不过还要维护乘法（暴力没有分！！），线段树不熟，挂了
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
typedef long long ll;
const ll mod=10007;
ll n,m;
ll a[100010],Jsum[500010],Csum[500010];
void build(ll k,ll l,ll r)//建树
{
if(l==r)
{
Jsum[k]=Csum[k]=a[l];
return;
}
ll mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
Jsum[k]=(Jsum[k<<1]+Jsum[k<<1|1])%mod;
Csum[k]=(Csum[k<<1]*Csum[k<<1|1])%mod;
}
void change(ll k,ll l,ll r,ll x,ll v)//更改数值
{
if(l==r)
{
Jsum[k]=Csum[k]=v;
return;
}
ll mid=(l+r)>>1;
if(x<=mid)change(k<<1,l,mid,x,v);
else change(k<<1|1,mid+1,r,x,v);
Jsum[k]=(Jsum[k<<1]+Jsum[k<<1|1])%mod;
Csum[k]=(Csum[k<<1]*Csum[k<<1|1])%mod;
}
ll queryC(ll k,ll l,ll r,ll x,ll y)//查询乘法
{
if(r<x||l>y)return 1;
if(x<=l&&r<=y)return Csum[k];
ll mid=(l+r)>>1;
ll res1,res2;
res1=queryC(k<<1,l,mid,x,y);
res2=queryC(k<<1|1,mid+1,r,x,y);
return (res1*res2)%mod;
}
ll queryJ(ll k,ll l,ll r,ll x,ll y)//查询加法
{
if(r<x||l>y)return 0;
if(x<=l&&r<=y)return Jsum[k];
ll mid=(l+r)>>1;
ll res1,res2;
res1=queryJ(k<<1,l,mid,x,y);
res2=queryJ(k<<1|1,mid+1,r,x,y);
return (res1+res2)%mod;
}
// 初始化部分
线段树真的特别长，而且特别容易写挂，在OJ上交了好几次0分的代码………………(还有一本通的线段树的模板题是不用写build()函数的……，于是把build()打挂提交了好几次)
附代码:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=100005;
int n,m,w[N];
struct node
{
int l,r;
LL sum,add;
}tree[N*4];
void pushup(int u)
{
tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;
}
void pushdown(int u)
{
auto &root=tree[u],&left=tree[u<<1],&right=tree[u<<1|1];
if(root.add)
{
left.add+=root.add;
left.sum+=(LL)(left.r-left.l+1)*root.add;
right.add+=root.add;
right.sum+=(LL)(right.r-right.l+1)*root.add;
root.add=0;
}
}
void build(int u,int l,int r)
{
if(l==r)tree[u]={l,r,w[r],0};
else
{
tree[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,int d)
{
if(tree[u].l>=l&&tree[u].r<=r)
{
tree[u].sum+=(LL)(tree[u].r-tree[u].l+1)*d;
tree[u].add+=d;
}
else
{
pushdown(u);
int mid=tree[u].l+tree[u].r>>1;
if(l<=mid)modify(u<<1,l,r,d);
if(r>mid)modify(u<<1|1,l,r,d);
pushup(u);
}
}
LL query(int u,int l,int r)
{
if(tree[u].l>=l&&tree[u].r<=r)return tree[u].sum;
pushdown(u);
int mid=tree[u].l+tree[u].r>>1;
LL sum=0;
if(l<=mid)sum+=query(u<<1,l,r);
if(r>mid)sum+=query(u<<1|1,l,r);
return sum;
}
//一些初始化......
不会的第二题……
[第三题]礼物
DP......
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005,mod=1e7+7;
int f[N][N],c[N];
int n,m,sum;
int main()
{
freopen("gift.in","r",stdin);
freopen("gift.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
sum+=c[i];
}
if(sum<=m)//特判所有物品价格的和不大于m的情况，此时只有一种方案
{
printf("1");
return 0;
}
sort(c+1,c+n+1);//设f[i][j]表示考虑前i件物品，剩余j元的方案数
f[n][c[n]]=1;
f[n][0]=1;
for(int i=n;i>=1;i--)
{
for(int j=0;j<=m;j++)
{
if(j>=c[i])f[i][j]=(f[i][j]+f[i+1][j-c[i]])%mod;
f[i][j]=(f[i][j]+f[i+1][j])%mod;
}
}
int rest=0,ans=0;
for(int k=1;k<=n;k++)
{
rest=m;
for(int i=1;i<k;i++)rest-=c[i];
if(rest<0)break;
for(int i=max(rest-c[k]+1,0);i<=rest;i++)ans=(ans+f[k+1][i])%mod;
}
printf("%d",ans);
return 0;
}
[第四题]宋伊雪的惩罚
长乐OJ原题，枚举中心点，二分最大的边长，判断相等时用二维HASH，真是不错的一道题目呢
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005;
int n,m;
typedef unsigned long long ULL;
const ULL base1=87,base2=31;//模数随便取（要质数）
ULL a[N][N],b[N][N],c[N][N],Hasha[N][N],Hashb[N][N],Hashc[N][N],fact1[N],fact2[N],ans;
bool check(int len,int x,int y)
{
if(x>n||y>m||x<len||y<len)return 0;
ULL HASHa=0,HASHb=0,HASHc=0;
HASHa=Hasha[x][y]-Hasha[x-len][y]*fact2[len]-Hasha[x][y-len]*fact1[len]+Hasha[x-len][y-len]*fact1[len]*fact2[len];
int t=y;
y=m-(y-len);
HASHb=Hashb[x][y]-Hashb[x-len][y]*fact2[len]-Hashb[x][y-len]*fact1[len]+Hashb[x-len][y-len]*fact1[len]*fact2[len];
y=t;
x=n-(x-len);
HASHc=Hashc[x][y]-Hashc[x-len][y]*fact2[len]-Hashc[x][y-len]*fact1[len]+Hashc[x-len][y-len]*fact1[len]*fact2[len];
return HASHa==HASHb&&HASHb==HASHc;
}
ULL B(int i,int j,int x=0)
{
int l=0,r=min(i,j)+f,Ans=x;
while(l<=r)
{
int mid=l+r>>1;
if(check(mid*2-x,i+mid,j+mid))
{
l=mid+1;
Ans=mid*2-x;
}
else r=mid-1;
}
return (Ans+1)/2;
}
int main()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d%d",&n,&m);
fact1[0]=fact2[0]=1ULL;
for(int i=1;i<=n;i++)fact1[i]=fact1[i-1]*base1;
for(int i=1;i<=m;i++)fact2[i]=fact2[i-1]*base2;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
b[i][m-j+1]=c[n-i+1][j]=a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
Hasha[i][j]+=Hasha[i][j-1]*base1+a[i][j];
Hashb[i][j]+=Hashb[i][j-1]*base1+b[i][j];
Hashc[i][j]+=Hashc[i][j-1]*base1+c[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
Hasha[i][j]+=Hasha[i-1][j]*base2;
Hashb[i][j]+=Hashb[i-1][j]*base2;
Hashc[i][j]+=Hashc[i-1][j]*base2;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)ans+=B(i,j,1)+B(i,j);
}
printf("%llu",ans);
return 0;
}
一涉及提高组字数就多到爆炸......
国庆集训DAY3
今天的题目又加强了
石子合并
第一题，一道分析题，看懂了就简单。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
a[i] = read();
if(a[i]>0)
{
zs++;
zx = min(zx,a[i]);
zz += a[i];
}
if(a[i]<0)
{
a[i] = abs(a[i]);
fs++;
fd = min(fd,a[i]);
fz += a[i];
a[i] -= 2*a[i];
}
if(a[i]==0)zl = 1;
}
if(n==1)
{
cout<<a[1]<<endl;
continue;
}
else if((zs&&fs)||zl == 1)
ans = zz + fz;
else if(zs)
ans = zz-2*zx;
else if(fs)
ans = fz-2*fd;
铺地毯
第二题。看一眼数据范围：1≤n≤3×105,1≤P,Q≤109,1≤T≤5
。
哦这不是我能打出来的。
优美的旋律
第三题，判断重复字符子串个数，按照题目要求去算。
是个能看懂的题目。
我用了一手string.find()
这很不错。
直接暴力拿下60分。
第四题不讲。
顺带提一句，今天的数据坑人
，每个测试点多个数据
一个不小心就没了
国庆集训DAY2
谈谈今天的题目。
第一题简单题，两个单元最短路然后选择一个最短组合。
第二题打爆力60分，（正解比较难思考）
第三、第四题，我根本看不懂……
综上，我也不知道我怎么弄的样例分。
中转站
算一个模板题。按上面的说法做就完了。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
ll u,v,w;
ll next;
}zz[2*M];
void jy(ll u,ll v,ll w)
{
pos++;
zz[pos].u = u;
zz[pos].v = v;
zz[pos].w = w;
zz[pos].next = head[zz[pos].u];
head[zz[pos].u] = pos;
return;
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q;
ll dis[N];
ll vis[N];
void Dij(ll from)
{
ll u;
for(int i=1;i<=n;i++)
{
dis[i]=1e13;vis[i] = 0;
}
dis[from] = 0;
q.push(make_pair(0,from));
while(!q.empty())
{
u = q.top().second;
q.pop();
if(vis[u])continue;
vis[u] = 1;
for(ll i=head[u];i;i=zz[i].next)
{
if(dis[zz[i].v]>dis[zz[i].u]+zz[i].w)
{
dis[zz[i].v] = dis[zz[i].u]+zz[i].w;
q.push(make_pair(dis[zz[i].v],zz[i].v));
}
}
}
for(int i=1;i<=k;i++)
{
if(from==s)c[r[i]] = dis[r[i]];
else ans = min(ans,c[r[i]]+dis[r[i]]);
}
return;
}
粒子自撞机
一个数学题。
用扩展欧几里得来求正解。
这是欧几里得模板
正解我也不会。
国庆集训DAY 1
今天的题目很有意思
水题但是看不出来。
难题又难到不会。
这边说前两题
破门而入(broken)
分析一下题目，其实这只输入两个数的，一般都是有规律的，因为数据范围比较大就有这个考虑。（就是考试我也没看出来）
分析多一个点的情况下，会不会多一个环，就可以弄出递推式。
2
3
4
5
for(int i=2;i<=n;i++)f[i][1] = f[i-1][1]*(i-1)%N;
for(int i=2;i<=n;i++)
for(int j=2;j<=k;j++)
f[i][j] = (f[i-1][j]*(i-1)+f[i-1][j-1])%N;
翻转游戏(turn)
我的考试时思路很简单，就是暴力（翻转，哈希）。
谁知道到这玩意也能有规律。
先求出所有的变法个数（只翻转一个的不算，但是只翻转一个的也就一种答案情况）
然后减去所有字母的（个数*个数减一）/2，就是减去所有翻转后无用的情况。
再然后
……
就没有然后了。
2
3
for(int i=97;i<=122;i++)
ans -= a[i]*(a[i]-1)/2;
P5304
啊，这题其实比较简单。
然后对于这个程序
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
inline long long read(){long long x;scanf("%lld",&x);return x;}
const long long N=15+5,M=75+5,inf=1e15;
long long T,n,m,k,in[N],ans;
long long fir[N],pre[M],nex[M],to[M],val[M],pos=0;
void add(long long x,long long y,long long v){
to[++pos]=y;pre[pos]=x;nex[pos]=fir[x];fir[x]=pos;val[pos]=v;
}
void _delete(long long x){
long long u=pre[x];
fir[u]=nex[fir[u]];
pre[x]=nex[x]=to[x]=val[x]=0;
}
void clear(){
memset(in,0,sizeof(in));
memset(fir,0,sizeof(fir));
memset(nex,0,sizeof(nex));
memset(to,0,sizeof(to));
memset(val,0,sizeof(val));
pos=0;ans=inf;n=m=k=0;
}
struct node{long long dian,far;}c;
bool operator <(node a,node b){return a.far>b.far;}
priority_queue<node> q;
long long dis[N],s,t;
long long dijk(){
for(int i=s;i<=t;++i) dis[i]=inf;
long long u=s;dis[s]=0;
c.dian=s;c.far=0;q.push(c);
while(!q.empty()){
c=q.top();q.pop();u=c.dian;
if(u==t) break;
if(c.far>dis[c.dian])continue;
for(long long i=fir[u];i;i=nex[i]){
long long v=to[i];
if(dis[u]+val[i]>=dis[v]) continue;
dis[v]=dis[u]+val[i];
c.dian=to[i];c.far=dis[v];
q.push(c);
}
}
while(!q.empty()) q.pop();
return dis[t];
}
int main(){
freopen("in.txt","r",stdin);
T=read();
while(T--){
clear();
n=read(),m=read(),k=read();
for(long long i=1;i<=m;++i){
long long x=read(),y=read(),z=read();
if（x!=y) add(x,y,z);
}
for(long long i=1;i<=k;++i)
in[read()]=1;
s=0,t=n+1;
for(long long l=1;l<=n;l<<=1){
for(long long u=1;u<=n;++u)
if(in[u])
u&l?add(s,u,0):add(u,t,0);
ans=min(ans,dijk());
for(long long i=m+1;i<=pos;++i)
_delete(i);
pos=m;
}
for(long long l=1;l<=n;l<<=1){
for(long long u=1;u<=n;++u)
if(in[u])
u&l?add(u,t,0):add(s,u,0);
ans=min(ans,dijk());
for(long long i=m+1;i<=pos;++i)
_delete(i);
pos=m;
}
printf("%lld\n",ans);
}
return 0;
}
它是错的
跑得时候会跑出dis[t]=0来
原因是实际的边数没有m条，在pos-m编号的临时边没有被删去