浪了一发普及模拟赛
题面见此
[样例输入]
4
1 1
2 1
1 1
[样例输出]
20
[数据规模和范围]
对于 30% 的数据, n≤1000.
对于另外 30% 的数据, bi=1.
对于 100% 的数据, n≤1 000 000,bi≤1000.
sol: 单边记贡献,(x,y) 边的贡献就是 Size[y]*(n-Size[y])*Dis[x][y], 因为父亲都小于当前点, 直接倒着跑一遍记 Size 就可以了, 如果无序的话可以用拓扑
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- inline ll read()
- {
- ll S=0;
- bool f=0;
- char ch=' ';
- while(!isdigit(ch))
- {
- f|=(ch=='-'); ch=getchar();
- }
- while(isdigit(ch))
- {
- S=(S<<3)+(S<<1)+(ch-'0'); ch=getchar();
- }
- return (f)?(-S):(S);
- }
- #define R(x) x=read()
- inline void write(ll x)
- {
- if(x<0)
- {
- putchar('-'); x=-x;
- }
- if(x<10)
- {
- putchar(x+'0'); return;
- }
- write(x/10); putchar(x%10+'0');
- return;
- }
- #define W(x) write(x),putchar(' ')
- #define Wl(x) write(x),putchar('\n')
- const int N=1000005;
- int n,Father[N],Size[N];
- int Val[N];
- int main()
- {
- freopen("fst.in","r",stdin);
- freopen("fst.out","w",stdout);
- int i;
- ll ans=0;
- R(n);
- for(i=1;i<=n;i++)
- {
- Size[i]=1;
- }
- for(i=2;i<=n;i++)
- {
- Father[i]=read(); Val[i]=read();
- }
- for(i=n;i>1;i--)
- {
- Size[Father[i]]+=Size[i];
- }
- for(i=2;i<=n;i++)
- {
- ans+=1ll*Val[i]*Size[i]*(n-Size[i]);
- }
- Wl(ans<<1);
- return 0;
- }
- /*
- input
- 5
- 1 2
- 2 4
- 2 1
- 4 4
- output
- 92
- input
- 5
- 1 5
- 1 5
- 2 3
- 2 5
- output
- 164
- */
- View Code
2. 贰 (fstagain)
[题目描述]
给你一个长度为 n 的序列, 有 m 次询问, 让你求区间 gcd.
[输入格式]
输入文件为 fstagain.in. 第一行两个正整数 n 和 m. 第二行 n 个正整数 ai, 保证 ai≤1 000 000 000. 接下来 m 行, 每行两个正整数 l 和 r, 询问序列中 l 到 r 的 gcd.
[输出格式]
输出文件为 fst.in. 输出 m 行, 表示查询的结果.
[样例输入]
- 3 2
- 3 6 8
- 1 2
- 2 3
[样例输出]
3
2
[数据规模和范围]
对于 30% 的数据, n,m≤1000.
对于 60% 的数据, n≤1000.
对于 100% 的数据, n,m≤100000.
sol: 因为重复没关系, ST 表可以搞, 线段树应该也可以做 (反正是模板), 我写了分块 (反正都能过)
- #include <bits/stdc++.h>
- using namespace std;
- typedef int ll;
- inline ll read()
- {
- ll S=0;
- bool f=0;
- char ch=' ';
- while(!isdigit(ch))
- {
- f|=(ch=='-'); ch=getchar();
- }
- while(isdigit(ch))
- {
- S=(S<<3)+(S<<1)+(ch-'0'); ch=getchar();
- }
- return (f)?(-S):(S);
- }
- #define R(x) x=read()
- inline void write(ll x)
- {
- if(x<0)
- {
- putchar('-'); x=-x;
- }
- if(x<10)
- {
- putchar(x+'0'); return;
- }
- write(x/10); putchar(x%10+'0');
- return;
- }
- #define W(x) write(x),putchar(' ')
- #define Wl(x) write(x),putchar('\n')
- const int N=100005,B=355;
- int n,m,a[N];
- int Block,cnt,L[B],R[B],Gcd[B],Pos[N];
- inline int gcd(int x,int y)
- {
- return (!y)?(x):(gcd(y,x%y));
- }
- inline void Pre()
- {
- int i,j;
- Block=sqrt(n);
- cnt=n/Block+(bool)(n%Block);
- for(i=1;i<=cnt;i++)
- {
- L[i]=R[i-1]+1;
- R[i]=L[i]+Block-1;
- }
- R[cnt]=n;
- for(i=1;i<=cnt;i++)
- {
- Gcd[i]=a[L[i]];
- Pos[L[i]]=i;
- for(j=L[i]+1;j<=R[i];j++)
- {
- Pos[j]=i;
- Gcd[i]=gcd(Gcd[i],a[j]);
- }
- }
- return;
- }
- inline int Solve(int l,int r)
- {
- int i;
- int ql=Pos[l],qr=Pos[r];
- if(ql+1>=qr)
- {
- int ans=a[l];
- for(i=l+1;i<=r;i++)
- {
- ans=gcd(ans,a[i]);
- }
- return ans;
- }
- else
- {
- int ans=a[l];
- for(i=l+1;i<L[ql+1];i++)
- {
- ans=gcd(ans,a[i]);
- }
- for(i=ql+1;i<qr;i++)
- {
- ans=gcd(ans,Gcd[i]);
- }
- for(i=L[qr];i<=r;i++)
- {
- ans=gcd(ans,a[i]);
- }
- return ans;
- }
- }
- int main()
- {
- freopen("fstagain.in","r",stdin);
- freopen("fstagain.out","w",stdout);
- int i;
- R(n); R(m);
- for(i=1;i<=n;i++)
- {
- R(a[i]);
- }
- Pre();
- for(i=1;i<=m;i++)
- {
- int l=read(),r=read();
- Wl(Solve(l,r));
- }
- return 0;
- }
- /*
- input
- 3 2
- 3 6 8
- 1 2
- 2 3
- output
- 3
- 2
- */
- View Code
3. 叁 (fstalways)
[题目描述]
有 4 种硬币, 面值分别为 c1,c2,c3,c4. 某人去商店买东西, 去 了 tot 次. 每次带 di 枚 ci 硬币, 买 s 的价值的东西. 求每次有多少 种付款方法.
[输入格式]
输入文件为 fstalways.in. 第一行 5 个正整数 c1,c2,c3,c4,tot. 接下来 tot 行, 每行 5 个正整数表示的 d1,d2,d3,d4,s.
[输出格式]
输出文件为 fstalways.out. 输出 tot 行, 表示每次的方案数.
[样例输入]
- 1 2 5 10 2
- 3 2 3 1 10
- 1000 2 2 2 900
[样例输出]
4
27
[数据规模和范围]
对于 30% 的数据, di≤10.
对于 50% 的数据, s,tot≤1000.
对于 100% 的数据, s≤1000000,tot≤100000.
sol: 先跑一遍没有 di 限制的背包, 然后容斥, 奇加偶减
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- inline ll read()
- {
- ll s=0;
- bool f=0;
- char ch=' ';
- while(!isdigit(ch))
- {
- f|=(ch=='-'); ch=getchar();
- }
- while(isdigit(ch))
- {
- s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
- }
- return (f)?(-s):(s);
- }
- #define R(x) x=read()
- inline void write(ll x)
- {
- if(x<0)
- {
- putchar('-'); x=-x;
- }
- if(x<10)
- {
- putchar(x+'0'); return;
- }
- write(x/10);
- putchar((x%10)+'0');
- return;
- }
- #define W(x) write(x),putchar(' ')
- #define Wl(x) write(x),putchar('\n')
- int C[5],D[5];
- ll dp[1000005];
- int main()
- {
- freopen("fstalways.in","r",stdin);
- freopen("fstalways.out","w",stdout);
- int i,j,T,Sum;
- ll ans=0;
- for(i=1;i<=4;i++)
- {
- R(C[i]);
- }
- R(T);
- dp[0]=1;
- for(i=1;i<=4;i++)
- {
- for(j=C[i];j<=1000000;j++)
- {
- dp[j]+=dp[j-C[i]];
- }
- }
- while(T--)
- {
- ans=0;
- for(i=1;i<=4;i++)
- {
- R(D[i]);
- }
- R(Sum);
- for(i=0;i<=15;i++)
- {
- int SS=Sum,Bo=1;
- for(j=1;j<=4;j++) if(i&(1<<(j-1)))
- {
- SS-=C[j]*(D[j]+1);
- Bo^=1;
- }
- if(SS<0) continue;
- if(Bo) ans+=dp[SS]; else ans-=dp[SS];
- }
- Wl(ans);
- }
- return 0;
- }
- /*
- input
- 1 2 5 10 2
- 3 2 3 1 10
- 1000 2 2 2 900
- output
- 4
- 27
- */
- View Code
来源: http://www.bubuko.com/infodetail-2965990.html