CodeForces 758

思路

A

扫一遍取最大值,减一减,加一加

B

哦这题有个奇妙的性质,好像是以前做别的题我发现的

为了保证任意连续四位字母不同

所以RBYG四个字母的下标模4后的余数必然不同,而且固定

所以。。。做完了2333333

C

写了一会,算出点了几个整行,点了几个整循环

然后数据规模就骤然减小,然后模拟,然后做完了

D

群聚讨论的结果,这题是真的贪心,假的DP233333

贪心思路很简单,从后往前能不进位就不进位,0要特殊处理

DP的话从后向前DP,dp[i]表示从i位往后到结尾进制转换后有几位

如果直接转移答案的话会爆LL,这个很麻烦,需要注意

感谢qwb聚聚的提示233333

E

看题姐领悟精神,但千万别照着题解写= =

可以看看qls的代码,然后变换一下思路

思路如下:

算出每条边的最小weight,然后从树根开始贪心地加上,能加多少是多少

如果有的边所需的最小weight小于等于0,那么无解

F

这题真的非常水= =然鹅比赛的时候来不及写了2333333

项数为1和2的特判暴力算掉

显然公比是有理数啊,说无理数的拖出去打死

然后我们不妨假设公比为$\frac{p}{q}$,其中$p$和$q$互质

那么我们可以想像

假设首项为$k$,末项为$k*{(\frac{p}{q})}^{n-1}$

考虑到$p$和$q$互质,那么显然$q^{n-1}|k$

由此令$k=sq^{n-1}$,那么数列末项为$sp^{n-1}$

显然其中$s$,$p$,$q$为正整数

于是我们可以估算p和q的范围都不会超过$r^{\frac{1}{n-1}}$

这很小啊!!!然后暴力枚举$p$和$q$,算出来满足要求的$s$有多少个即可

开方运算请注意手动的话可能会爆$long long$,所以请加上特判

代码

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int ans,n,i,m;
int a[105];

int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
m=max(a[i],m);
}
for(i=1;i<=n;i++)ans+=m-a[i];
printf("%d",ans);
return 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
map<int,char> m1;
map<char,int> m2;
char s[105];
int n,i,j,k;
int main()
{
gets(s+1);n=strlen(s+1);
for(i=1;i<=n;i++)
if(s[i]!='!')m1[i%4]=s[i];
for(i=1;i<=n;i++)
{
if(s[i]!='!')continue;
m2[m1[i%4]]++;
}
printf("%d %d %d %d",m2['R'],m2['B'],m2['Y'],m2['G']);
return 0;
}

C

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
LL n,m,k,x,y;
LL ma,mi,tot;
LL a[105];

int main()
{
scanf("%lld %lld %lld %lld %lld",&n,&m,&k,&x,&y);
LL p=k/m;LL la=k-m*p;
if(n==1)
{
if(m*p<k)ma=p+1;else ma=p;
mi=p;
k-=m*p;
if(y<=k)tot=ma;else tot=mi;
printf("%lld %lld %lld",ma,mi,tot);
return 0;
}
LL o=p/(2*n-2);
p-=o*(2*n-2);
for(int i=2;i<=n-1;i++)a[i]=2*o;
a[1]=a[n]=o;ma=max(a[1],a[2]);
int j=0,q=1;
for(int i=1;i<=p;i++)
{
j+=q;
if(j==n)q=-1;
if(j==1)q=1;
a[j]++;
ma=max(ma,a[j]);
}
if(la>0)j+=q;
if(j==1 || j==n)
{
mi=min(a[1],a[n]);
if(x==j && y<=la)tot=a[x]+1;else tot=a[x];
if(la>0)ma=max(ma,a[j]+1);
}else
{
mi=min(a[1],a[n]);
if(la>0)ma=max(ma,a[j]+1);
if(x==j && y<=la)tot=a[x]+1;else tot=a[x];
}
printf("%lld %lld %lld",ma,mi,tot);
return 0;
}

D

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
LL ans;
char s[65];
LL a[100];
LL jz,now;
int i,j,k,l;
LL dp[100];
LL jl[100];
LL n;

int main()
{
scanf("%lld\n",&n);
gets(s+1);l=strlen(s+1);
for(i=l;i>=1;i--)
{
if(s[i]=='0')
{
dp[i]=dp[i+1]+1;
jl[i]=i+1;
continue;
}
now=s[i]-48;
dp[i]=500;
for(j=i+1;j<=l+1 && now<n;j++)
{
if(dp[j]+1<dp[i])
{
dp[i]=dp[j]+1;
jl[i]=j;
}
now=now*10+s[j]-48;
}
}
k=1;a[1]=1;j=1;
while(j!=l+1)
{
a[++k]=jl[j];
j=jl[j];
}
ans=0;jz=1;
for(i=k-1;i>=1;i--)
{
now=0;
for(j=a[i];j<=a[i+1]-1;j++)now=now*10+s[j]-48;
ans+=now*jz;
jz*=n;
}
printf("%lld",ans);
return 0;
}

E

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
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
88
89
90
91
92
93
94
95
96
97
98
const int maxn=200005;

struct edge
{
int v1,v2;
LL p,w;
}edg[maxn];
struct nex
{
int to,label;
nex(int to=0,int label=0):to(to),label(label){};
};
vector<nex>son[maxn],g[maxn];
bool vis[maxn];
LL aw[maxn],ap[maxn],as[maxn];
int n;

void findson(int now)
{
vis[now]=true;
for(unsigned int i=0;i<g[now].size();i++)
{
int v=g[now][i].to;
if(vis[v])continue;
son[now].push_back(g[now][i]);
}
for(unsigned int i=0;i<son[now].size();i++)
findson(son[now][i].to);
}

void cal(int now)
{
if(son[now].size()==0)return;
for(unsigned int i=0;i<son[now].size();i++)cal(son[now][i].to);
for(unsigned int i=0;i<son[now].size();i++)
{
struct nex v=son[now][i];
int id=v.label;
ap[id]=as[v.to];
aw[id]=edg[id].w+(ap[id]-edg[id].p);
if(aw[id]<=0)
{
ap[id]+=1-aw[id];
aw[id]=1;
}
if(ap[id]>edg[id].p){printf("-1");exit(0);}
as[now]+=as[v.to]+aw[id];
}
}

LL solve(int now,LL need)
{
LL sum=0;
for(unsigned int i=0;i<son[now].size();i++)
{
struct nex v=son[now][i];
int id=v.label;
if(need<=edg[id].p-ap[id])
{
ap[id]+=need;
aw[id]+=need;
sum+=need;
need=0;
}else
{
need-=(edg[id].p-ap[id]);
aw[id]+=(edg[id].p-ap[id]);
sum+=(edg[id].p-ap[id]);
ap[id]=edg[id].p;
}
LL tmp=0;
tmp=solve(v.to,min(need,ap[id]-as[v.to]));
need-=tmp;
sum+=tmp;
}
return sum;
}

int main()
{
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
scanf("%lld%lld",&edg[i].w,&edg[i].p);
edg[i].v1=x;edg[i].v2=y;
g[x].push_back(nex(y,i));
g[y].push_back(nex(x,i));
}
memset(vis,0,sizeof(vis));
findson(1);
cal(1);solve(1,1e18);
printf("%d\n",n);
for(int i=1;i<=n-1;i++)
printf("%d %d %lld %lld\n",edg[i].v1,edg[i].v2,aw[i],ap[i]);
return 0;
}

F

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
61
62
63
64
65
66
67
68
69
LL n,l,r;
LL i,j,k,m,ans;

LL mi(LL x,LL y)
{
LL ans=1;
while(y>0)
{
if(y&1)ans*=x;
x*=x;
y>>=1;
}
return ans;
}

LL find(LL x,LL y)
{
if(x>=25)return 1;
LL t=x;
LL u=y;
while(t>1)
{
y=(LL)(sqrt(y)+1);
t>>=1;
}
LL ll=1,rr=y;
while(rr-ll>1)
{
LL mid=(ll+rr)>>1;
if(mi(mid,x)>u)rr=mid;else ll=mid;
}
if(mi(rr,x)>u)rr--;
return rr;
}

LL gcd(LL x,LL y)
{
if(x==0)return y;
if(y==0)return x;
return gcd(y,x%y);
}

int main()
{
scanf("%lld %lld %lld",&n,&l,&r);
if(n==1){printf("%lld",r-l+1);return 0;}
if(n==2)
{
LL len=r-l+1;
printf("%lld",len*(len-1));
return 0;
}
LL xr=find(n-1,r);
for(i=2;i<=xr;i++)
{
for(j=1;j<i;j++)
{
if(gcd(i,j)!=1)continue;
LL p=mi(i,n-1);
LL q=mi(j,n-1);
LL le,ri;
if(l%q==0)le=l/q;else le=l/q+1;
ri=r/p;
if(ri>=le)ans+=(ri-le+1)*2;
}
}
printf("%lld",ans);
return 0;
}