2016湖南省赛 [Cloned]

湖南省赛 [Cloned]"/>

2016湖南省赛 [Cloned]

A.2016

给出正整数 n 和 m，统计满足以下条件的正整数对 (a,b) 的数量： 1. 1≤a≤n,1≤b≤m; 2. a×b 是 2016 的倍数。

Input

输入包含不超过 30 组数据。

 

每组数据包含两个整数 n,m (1≤n,m≤10  ⁹).

Output对于每组数据，输出一个整数表示满足条件的数量。Sample Input

32 63
2016 2016
1000000000 1000000000

Sample Output

1
30576
7523146895502644

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int vis[2020];
int main()
{int n,m;while(~scanf("%d%d",&n,&m)){memset(vis,0,sizeof(vis));ll ans=0;for(int i=2016;i>=1;i--){vis[i]+=n/i;for(int j=i-1;j>=1;j--){if(i%j==0)vis[j]-=vis[i];}ans+=1LL*vis[i]*(m/(2016/__gcd(2016,i)));}printf("%lld\n",ans);}
}

View Code

B. 有向无环图

Bobo 有一个 n 个点，m 条边的有向无环图（即对于任意点 v，不存在从点 v 开始、点 v 结束的路径）。 为了方便，点用 1,2,…,n 编号。 设 count(x,y) 表示点 x 到点 y 不同的路径数量（规定 count(x,x)=0），Bobo 想知道 除以 (10  ⁹+7) 的余数。 其中，a  _i,b  _j 是给定的数列。

Input

输入包含不超过 15 组数据。 每组数据的第一行包含两个整数 n,m (1≤n,m≤10  ⁵). 接下来 n 行的第 i 行包含两个整数 a  _i,b  _i (0≤a  _i,b  _i≤10  ⁹). 最后 m 行的第 i 行包含两个整数 u  _i,v  _i，代表一条从点 u  _i 到 v  _i 的边 (1≤u  _i,v _i≤n)。

Output对于每组数据，输出一个整数表示要求的值。Sample Input

3 3
1 1
1 1
1 1
1 2
1 3
2 3
2 2
1 0
0 2
1 2
1 2
2 1
500000000 0
0 500000000
1 2

Sample Output

4
4
250000014

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
const int maxn=1e5+10;
ll a[maxn],b[maxn],s[maxn];
vector<int>G[maxn];
int in[maxn],n,m;
void work()
{queue<int>P;for(int i=1;i<=n;i++){if(in[i]==0)P.push(i);}while(!P.empty()){int v=P.front();P.pop();for(int i=G[v].size()-1;i>=0;i--){int u=G[v][i];in[u]--;if(in[u]==0)P.push(u);s[u]=(s[u]+s[v])%mod;}}ll ans=0;for(int i=1;i<=n;i++)ans=(ans+(s[i]-a[i]+mod)*b[i])%mod;printf("%lld\n",ans);
}
int main()
{while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++){scanf("%lld%lld",&a[i],&b[i]);s[i]=a[i];}for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);in[y]++;}work();for(int i=1;i<=n;i++){G[i].clear();in[i]=0;}}return 0;
}

View Code

G.Parentthesis

Bobo has a balanced parenthesis sequence P=p  ₁ p  ₂…p  _n of length n and q questions. The i-th question is whether P remains balanced after p  _ai and p  _bi  swapped. Note that questions are individual so that they have no affect on others. Parenthesis sequence S is balanced if and only if: 1.  S is empty; 2.  or there exists balanced parenthesis sequence A,B such that S=AB; 3.  or there exists balanced parenthesis sequence S' such that S=(S').

Input

The input contains at most 30 sets. For each set: The first line contains two integers n,q (2≤n≤10  ⁵,1≤q≤10  ⁵). The second line contains n characters p  ₁ p  ₂…p  _n. The i-th of the last q lines contains 2 integers a  _i,b  _i (1≤a  _i,b  _i≤n,a  _i≠b  _i).

 

OutputFor each question, output " Yes" if P remains balanced, or " No" otherwise.Sample Input

4 2
(())
1 3
2 3
2 1
()
1 2

Sample Output

No
Yes
No

代码（括号匹配终于会啦）：

#include <bits/stdc++.h>
using namespace std;const int maxn = 1e5 + 10;
int N, Q;
string s;
int sum[maxn], vis[maxn], a[maxn];int main() {while(~scanf("%d%d", &N, &Q)) {memset(sum, 0, sizeof(sum));cin >> s;for(int i = 0; s[i]; i ++) {if(s[i] == '(') a[i] = 1;else a[i] = -1;}memset(vis, 0, sizeof(vis));for(int i = 0; s[i]; i ++) {if(i == 0) sum[i] = a[i];else sum[i] = sum[i - 1] + a[i];}for(int q = 0; q < Q; q ++) {int l, r;scanf("%d%d", &l, &r);l -= 1, r -= 1;if(s[l] == s[r]) printf("Yes\n");else {if(s[r] == ')') if(sum[l] - 2 < 0 || sum[r] - 2 < 0) printf("No\n");else printf("Yes\n");}}}return 0;
}

View Code

H. Reverse

Bobo has a n digits decimal number D=d  ₁ d  ₂…d  _n (It may have leading zeros). Let R(i,j) denotes number D with digits between the i-th position and j-th position reversed. That is, R(i,j)=d  ₁…d  _i-1 d  _j d  _j-1…d  _i d  _j+1 d  _j+2…d  _n. Bobo would like to find modulo (10  ⁹+7).

Input

The input contains at most 30 sets. For each set: The first line contains an integer n (1≤n≤10  ⁵). The second line contains n digits d  ₁ d  ₂…d  _n (0≤d  _i≤9).

OutputFor each set, an integer denotes the result.Sample Input

2
12
3
012
10
0123456789

Sample Output

45
369
733424314

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
ll pow1(ll a,ll b)
{ll r=1;while(b){if(b&1)r=r*a%mod;a=a*a%mod;b/=2;}return r;
}
ll inv_9=pow1(9,mod-2);
ll p[100005];
char t[100005];
int main()
{p[0]=1;for(int i=1;i<=100000;i++)p[i]=p[i-1]*10%mod;int n;while(~scanf("%d",&n)){scanf("%s",t+1);reverse(t+1,t+n+1);ll ans=0;for(int i=1;i<=n;i++){ll v=t[i]-'0';ans+=(1LL*(i-1)+1LL*(i-1)*(i-2)/2)%mod*v%mod*p[i-1]%mod;ans+=(1LL*(n-i)+1LL*(n-i)*(n-i-1)/2)%mod*v%mod*p[i-1]%mod;ans%=mod;ll tmp=v*(p[i]-1+mod)%mod*inv_9%mod;tmp=tmp*(p[n-i+1]-1+mod)%mod*inv_9%mod;ans+=tmp;ans%=mod;}printf("%lld\n",ans);}return 0;
}

View Code

I.Tree Intersection

Bobo has a tree with n vertices numbered by 1,2,…,n and (n-1) edges. The i-th vertex has color c  _i, and the i-th edge connects vertices a  _i and b  _i. Let C(x,y) denotes the set of colors in subtree rooted at vertex x deleting edge (x,y). Bobo would like to know R_i which is the size of intersection of C(a  _i,b  _i) and C(b _i,a  _i) for all 1≤i≤(n-1). (i.e. |C(a  _i,b  _i)∩C(b  _i,a  _i)|)

Input

The input contains at most 15 sets. For each set: The first line contains an integer n (2≤n≤10  ⁵). The second line contains n integers c  ₁,c  ₂,…,c  _n (1≤c_i≤n). The i-th of the last (n-1) lines contains 2 integers a  _i,b  _i (1≤a  _i,b  _i≤n).

OutputFor each set, (n-1) integers R ₁,R ₂,…,R _n-1.Sample Input

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

Sample Output

1
2
1
1
1
2
1

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>G[maxn],id[maxn];
int a[maxn],ans[maxn],s[maxn],now[maxn],son[maxn],sz[maxn],cnt;
void get_son(int v,int fa)
{sz[v]=1;son[v]=0;for(int i=G[v].size()-1;i>=0;i--){int u=G[v][i];if(u==fa)continue;get_son(u,v);sz[v]+=sz[u];if(sz[u]>sz[son[v]])son[v]=u;}
}
void work1(int v,int fa)
{now[a[v]]++;if(now[a[v]]==1&&s[a[v]]>1)cnt++;else if(now[a[v]]==s[a[v]]&&now[a[v]]>1)cnt--;for(int i=G[v].size()-1;i>=0;i--){int u=G[v][i];if(u==fa)continue;work1(u,v);}
}
void work2(int v,int fa)
{now[a[v]]--;if(now[a[v]]==0&&s[a[v]]>1)cnt--;else if(now[a[v]]==s[a[v]]-1&&now[a[v]]>0)cnt++;for(int i=G[v].size()-1;i>=0;i--){int u=G[v][i];if(u==fa)continue;work2(u,v);}
}
void dfs(int v,int fa,int flag,int q)
{int I;for(int i=G[v].size()-1;i>=0;i--){int u=G[v][i];if(u==son[v])I=id[v][i];if(u==fa||u==son[v])continue;dfs(u,v,0,id[v][i]);}if(son[v])dfs(son[v],v,1,I);for(int i=G[v].size()-1;i>=0;i--){int u=G[v][i];if(u==fa||u==son[v])continue;work1(u,v);}now[a[v]]++;if(now[a[v]]==1&&s[a[v]]>1)cnt++;else if(now[a[v]]==s[a[v]]&&now[a[v]]>1)cnt--;ans[q]=cnt;if(flag==0)work2(v,fa);
}
int main()
{int n;while(~scanf("%d",&n)){memset(s,0,sizeof(s));memset(now,0,sizeof(now));for(int i=1;i<=n;i++)scanf("%d",&a[i]),s[a[i]]++;for(int i=1,x,y;i<n;i++){scanf("%d%d",&x,&y);G[x].push_back(y);id[x].push_back(i);G[y].push_back(x);id[y].push_back(i);}get_son(1,0);cnt=0;dfs(1,0,0,0);for(int i=1;i<=n;i++){G[i].clear();id[i].clear();if(i<n)printf("%d\n",ans[i]);ans[i]=0;}}
}

View Code

J.三角形和矩形

Bobo 有一个三角形和一个矩形，他想求他们交的面积。 具体地，三角形和矩形由 8 个整数 x  ₁,y  ₁,x  ₂,y  ₂,x  ₃,y  ₃,x  ₄,y  ₄ 描述。 表示三角形的顶点坐标是 (x  ₁,y  ₁),(x  ₁,y  ₂),(x  ₂,y  ₁)， 矩形的顶点坐标是 (x  ₃,y  ₃),(x  ₃,y  ₄),(x  ₄,y ₄),(x  ₄,y  ₃).

Input

输入包含不超过 30000 组数据。 每组数据的第一行包含 4 个整数 x  ₁,y  ₁,x  ₂,y  ₂ (x  ₁≠x  ₂,y  ₁≠y  ₂). 第二行包含 4 个整数 x  ₃,y  ₃,x  ₄,y  ₄ (x  ₃<x  ₄,y  ₃<y  ₄). (0≤x  _i,y  _i≤10  ⁴)

Output对于每组数据，输出一个实数表示交的面积。绝对误差或相对误差小于 10 ^-6 即认为正确。Sample Input

1 1 3 3
0 0 2 2
0 3 3 1
0 0 2 2
4462 1420 2060 2969
4159 257 8787 2970

Sample Output

1.00000000
0.75000000
439744.13967527

代码：

#include<bits/stdc++.h>
using namespace std;
double k,b;
double cal1(double Y1,double Y2,double y,double xx1,double xx2)
{if(y>=Y2) return 0;double h=(y-b)/k;if(y>=Y1&&y<Y2)return (xx2-h)*(Y2-y)*0.5;return ((Y1-y)+(Y2-y))*(xx2-xx1)*0.5;
}
double cal2(double Y1,double Y2,double y,double xx1,double xx2)
{if(y<=Y2) return 0;double h=(y-b)/k;if(y>Y2&&y<=Y1)return (y-Y2)*(xx2-h)*0.5;return ((y-Y1)+(y-Y2))*(xx2-xx1)*0.5;
}
double cal3(double Y1,double Y2,double y,double xx1,double xx2)
{if(y>=Y1) return 0;double h=(y-b)/k;if(y>=Y2&&y<Y1)return (Y1-y)*(h-xx1)*0.5;return ((Y1-y)+(Y2-y))*(xx2-xx1)*0.5;
}
double cal4(double Y1,double Y2,double y,double xx1,double xx2)
{if(y<=Y1) return 0;double h=(y-b)/k;if(y>Y1&&y<=Y2)return (y-Y1)*(h-xx1)*0.5;return ((y-Y1)+(y-Y2))*(xx2-xx1)*0.5;
}
int main()
{int x1,y1,x2,y2,x3,y3,x4,y4;while(~scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4)){int xx1=max(min(x1,x2),x3),xx2=min(max(x1,x2),x4);int yy1=max(min(y1,y2),y3),yy2=min(max(y1,y2),y4);k=1.0*(y2-y1)/(x1-x2),b=1.0*y2-k*x1;if(xx1>=xx2||yy1>=yy2)printf("0.0000000000000\n");else if(y2>y1&&x1>x2){double Y1=k*xx1+b,Y2=k*xx2+b;double ans=cal1(Y1,Y2,1.0*yy1,1.0*xx1,1.0*xx2)-cal1(Y1,Y2,1.0*yy2,1.0*xx1,1.0*xx2);printf("%.10lf\n",ans);}else if(y2<y1&&x2<x1){double Y1=k*xx1+b,Y2=k*xx2+b;double ans=cal2(Y1,Y2,1.0*yy2,1.0*xx1,1.0*xx2)-cal2(Y1,Y2,1.0*yy1,1.0*xx1,1.0*xx2);printf("%.10lf\n",ans);}else if(x2>x1&&y2>y1){double Y1=k*xx1+b,Y2=k*xx2+b;double ans=cal3(Y1,Y2,1.0*yy1,1.0*xx1,1.0*xx2)-cal3(Y1,Y2,1.0*yy2,1.0*xx1,1.0*xx2);printf("%.10lf\n",ans);}else{double Y1=k*xx1+b,Y2=k*xx2+b;double ans=cal4(Y1,Y2,1.0*yy2,1.0*xx1,1.0*xx2)-cal4(Y1,Y2,1.0*yy1,1.0*xx1,1.0*xx2);printf("%.10lf\n",ans);}}
}

View Code

 

明天省赛 加油啦 希望有好结果

今日份的瘦宅茶 

喜茶最近出的芝芝桃桃和多肉粉荔都没时间去喝！！！不是合格的 HEYTEA Girl 了！！！快放假吧

转载于:.html