Rank13，解题数9题，队友带飞
Cotree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Avin has two trees which are not connected. He asks you to add an edge between them to make them connected while minimizing the function ∑ni=1∑nj=i+1dis(i,j), where dis(i,j) represents the number of edges of the path from i to j. He is happy with only the function value.
InputThe first line contains a number n (2<=n<=100000). In each of the following n−2 lines, there are two numbers u and v, meaning that there is an edge between uand v. The input is guaranteed to contain exactly two trees.
OutputJust print the minimum function value.
Sample Input
3 1 2
Sample Output
4
待补
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
int f,t,nxt;
};
edge e[400400];
int n,head[100100],du[100100],vis[100100],cnt=1;
void add_edge(int f,int t){
e[cnt]=(edge){f,t,head[f]};
head[f]=cnt;
cnt++;
return;
}
queue<int> q;
int pre[100100];int th=0;
int bfs(int st){
th=0;
while(!q.empty()) q.pop();
q.push(st);
vis[st]=1;
int la=st;
while(!q.empty()){
int x=q.front();
th++;
la=x;
q.pop();
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].t;
if(!vis[v]){
vis[v]=1;
pre[v]=x;
q.push(v);
}
}
}
return la;
}
vector<int> v;
int dis[100100];
ll suf[100100],pp[100100];
ll fi(int st){
memset(vis,0,sizeof(vis));
int ed=bfs(st);
memset(pre,0,sizeof(pre));
memset(vis,0,sizeof(vis));
st=bfs(ed);
memset(vis,0,sizeof(vis));
v.clear();
int tmp=st;
while(pre[tmp]){
vis[tmp]=1;
v.push_back(tmp);
tmp=pre[tmp];
}
vis[tmp]=1;
v.push_back(tmp);
memset(dis,0,sizeof(dis));
memset(suf,0,sizeof(suf));
memset(pp,0,sizeof(pp));
for(int i=0;i<(int)v.size();i++){
bfs(v[i]);
dis[i+1]=th;
}
int lim=(int)v.size();
ll pre=0;
for(int i=1;i<=lim;i++){
pp[i]=pp[i-1]+1ll*pre;
pre+=1ll*dis[i];
}
pre=0;
for(int i=lim;i>=1;i--){
suf[i]=suf[i+1]+pre;
pre+=1ll*dis[i];
}
ll mi=suf[1]+pp[1];
int pt=1;
for(int i=1;i<=lim;i++){
if(suf[i]+pp[i]<mi){
pt=i;
mi=suf[i]+pp[i];
}
}
return v[pt-1];
}
int erzi[100100];
int dfs(int pos){
vis[pos]=1;
int cnt=1;
for(int i=head[pos];i;i=e[i].nxt){
int v=e[i].t;
if(!vis[v]){
cnt+=dfs(v);
}
}
erzi[pos]=cnt;
return cnt;
}
int main(){
while(scanf("%d",&n)!=EOF){
cnt=1;
memset(head,0,sizeof(head));
memset(du,0,sizeof(du));
for(int i=n-2;i>=1;i--){
int f,t;
scanf("%d%d",&f,&t);
add_edge(f,t);
add_edge(t,f);
du[f]++;du[t]++;
}
int pt=0;
for(int i=1;i<=n;i++){
if(du[i]==1){
pt=i;
break;
}
}
int p1,p2;
p1=fi(pt);
for(int i=1;i<=n;i++){
if(vis[i]==0){
pt=i;
break;
}
}
p2=fi(pt);
add_edge(p1,p2);
add_edge(p2,p1);
memset(erzi,0,sizeof(erzi));
memset(vis,0,sizeof(vis));
dfs(p1);
ll ans=0;
for(int i=1;i<=n;i++){
ans+=1ll*(n-erzi[i])*erzi[i];
}
printf("%lld\n",ans);
}
return 0;
}
Trap
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Avin is studying isosceles trapezoids. An isosceles trapezoid is a convex quadrilateral with two opposite parallel bases, two equal-length legs and positive area. In this problem, we further require that the two legs are not parallel. Given n segments, you are asked to find the number of isosceles trapezoids whose 4 edges are from these segments and the greatest common divisor of their lengths is 1. Two congruent isosceles trapezoids are counted only once.
InputThe first line contains a number n (4 ≤ n ≤ 2, 000). The second line contains n numbers, each of which represents the length of a segment (the length is within [2, 10000]).
OutputPrint the number of non-congruent isosceles trapezoids.
Sample Input
5 4 4 2 8 9 6 4 4 4 2 8 9
Sample Output
2 3
暴力乱搞
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int a,b;
int c;
bool operator < (const node& y)const{
return c<y.c;
}
};
vector<node> v[10010];
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int num[2050],dis[10010];
int nn[2050];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
for(int i=0;i<10010;i++){
v[i].clear();
}
memset(dis,0,sizeof(dis));
for(int i=1;i<=n;i++){
scanf("%d",&num[i]);
dis[num[i]]++;
}
sort(num+1,num+1+n);
int pp=1;
for(int i=1;i<=n;i++){
if(num[i]!=nn[pp-1]){
nn[pp]=num[i];
pp++;
}
}
for(int i=1;i<pp;i++){
for(int j=i+1;j<pp;j++){
int g=gcd(nn[i],nn[j]);
v[g].push_back((node){max(nn[i],nn[j]),min(nn[i],nn[j]),abs(nn[i]-nn[j])});
}
}
for(int i=0;i<10010;i++){
sort(v[i].begin(),v[i].end());
}
ll ret=0;
for(int i=2;i<10010;i++){
int fg=0;
if(dis[i]<2) continue;
if(dis[i]==2) fg=1;
for(int j=1;j<10010;j++){
if(gcd(i,j)!=1) continue;
int ans=-1;
int ub=(int)v[j].size()-1;
int lb=0;
while(ub>=lb){
int md=(ub+lb)>>1;
if(v[j][md].c<i*2){
ans=md;
lb=md+1;
}
else{
ub=md-1;
}
}
if(fg){
for(int k=ans;k>=0;k--){
if(v[j][k].b==i || v[j][k].a==i){
ans--;
}
}
}
if(ans<=-1){
continue;
}
else{
ret+=1ll*(ans+1);
}
}
}
printf("%lld\n",ret);
}
return 0;
}
Wave
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Avin is studying series. A series is called "wave" if the following conditions are satisfied:
1) It contains at least two elements;
2) All elements at odd positions are the same;
3) All elements at even positions are the same;
4) Elements at odd positions are NOT the same as the elements at even positions.
You are given a series with length n. Avin asks you to find the longest "wave" subseries. A subseries is a subsequence of a series.
InputThe first line contains two numbers n, c (1 ≤ n ≤ 100, 000, 1 ≤ c ≤ 100). The second line contains n integers whose range is [1, c], which represents the series. It is guaranteed that there is always a "wave" subseries.
OutputPrint the length of the longest "wave" subseries.
Sample Input
5 3 1 2 1 3 2
Sample Output
4
待补
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
struct node{int num,cnt;} dp[110][110];
int a[maxn];
int main()
{
int n,c;
while (~scanf("%d%d",&n,&c))
{
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=c;i++)
for (int j=1;j<=c;j++) dp[i][j].cnt=0,dp[i][j].num=i;
for (int i=1;i<=n;i++)
{
int x=a[i];
for (int i=1;i<=c;i++)
{
if(x==i) continue;
if(dp[i][x].num==x) {dp[i][x].cnt++;dp[i][x].num=i;}
if(dp[x][i].num==x) {dp[x][i].cnt++;dp[x][i].num=i;}
}
}
int ans=0;
for (int i=1;i<=c;i++)
for (int j=1;j<=c;j++) ans=max(ans,dp[i][j].cnt);
printf("%d\n",ans);
}
return 0;
}
Packing
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Avin’s warehouse has a packing line with m outlets. There are n goods in total, which aren’t on the packing line. And the i-th good will be sent to the xi outlet at time ti . In each second, Avin can send at most one good from one outlet to the packing line. For outlet i, there is an associated buffer with size ai, and goods can be placed in the buffer. However, at the end of each second, if the number of goods b at the outlet is greater than ai , Avin has to pay the utilization fee b - ai . Since Avin wants to save money, he asks you to find a plan to send all the goods to the packing line with minimum utilization fee. In order to finish today’s work, Avin must send all goods to the packing line. Goods arrived at time ti can be sent to the packing line immediately at time ti.
InputThe first line contains two integers n and m (1 ≤ n, m ≤ 1, 000, 000) . In the following n lines, each of which contains two numbers ti (1 ≤ ti ≤ 1, 000, 000) and xi (1 ≤ xi ≤ m). In the next following line, there are m integers containing ai (1 ≤ ai ≤ 1, 000, 000).
OutputPrint the minimum utilization fee.
Sample Input
10 2 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1 2 1 2 1 2
Sample Output
21
贪心乱搞
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
int n,m,a[maxn],cnt[maxn];
struct node{
int t,x;
bool operator<(const node &b)const{return t<b.t;}
}p[maxn];
void solve(){
rep(i,1,n) scanf("%d%d",&p[i].t,&p[i].x);
sort(p+1,p+1+n);
rep(i,1,m) scanf("%d",&a[i]),cnt[i]=0;
int pos=1,op=0;
ll has=0,need=0,ans=0;
rep(t,1,p[n].t){
if(has>op||p[pos].t==t) op++;
while(need&&op) op--,has--,need--;
while(pos<=n&&p[pos].t==t){
int now=p[pos++].x;
cnt[now]++; has++;
if(cnt[now]>a[now]){
if(op) op--;
else need++;
cnt[now]--;
}
}
ans+=need;
}
if(need) ans+=need*(need-1)/2;
printf("%lld\n",ans);
}
int main(){
scanf("%d%d",&n,&m); solve();
}
String
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Avin has a string. He would like to uniform-randomly select four characters (selecting the same character is allowed) from it. You are asked to calculate the probability of the four characters being ”avin” in order.
InputThe first line contains n (1 ≤ n ≤ 100), the length of the string. The second line contains the string. To simplify the problem, the characters of the string are from ’a’, ’v’, ’i’, ’n’.
OutputPrint the reduced fraction (the greatest common divisor of the numerator and denominator is 1), representing the probability. If the answer is 0, you should output "0/1".
Sample Input
4 avin 4 aaaa
Sample Output
1/256 0/1
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n;
char str[110];
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
void solve(){
scanf("%s",str+1);
int cnt[27]={0,};
rep(i,1,n) cnt[str[i]-'a']++;
if(cnt['a'-'a']==0||cnt['v'-'a']==0||cnt['i'-'a']==0||cnt['n'-'a']==0){
printf("0/1\n");return;
}
int up=cnt['i'-'a']*cnt['n'-'a']*cnt['v'-'a']*cnt['a'-'a'];
int down=n*n*n*n;
int g=gcd(up,down);
printf("%d/%d\n",up/g,down/g);
}
int main(){
while(~scanf("%d",&n)) solve();
}
Traffic
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Avin is observing the cars at a crossroads. He finds that there are n cars running in the east-west direction with the i-th car passing the intersection at time ai . There are another m cars running in the north-south direction with the i-th car passing the intersection at time bi . If two cars passing the intersections at the same time, a traffic crash occurs. In order to achieve world peace and harmony, all the cars running in the north-south direction wait the same amount of integral time so that no two cars bump. You are asked the minimum waiting time.
InputThe first line contains two integers n and m (1 ≤ n, m ≤ 1, 000). The second line contains n distinct integers ai (1 ≤ ai ≤ 1, 000). The third line contains m distinct integers bi (1 ≤ bi ≤ 1, 000).
OutputPrint a non-negative integer denoting the minimum waiting time.
Sample Input
1 1 1 1 1 2 2 1 3
Sample Output
1 0
暴力模拟一下就好了
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,m,a[1100],b[1100];
void solve(){
rep(i,1,n) scanf("%d",&a[i]); sort(a+1,a+1+n);
rep(i,1,m) scanf("%d",&b[i]); sort(b+1,b+1+m);
set<int> v;
rep(i,1,n) if(a[i]-b[1]>=0) v.insert(a[i]-b[1]);
rep(i,2,m) for(auto u:v){
if(u-(b[i]-b[i-1])>=0) v.insert(u-(b[i]-b[i-1]));
}
rep(i,0,1000) if(!v.count(i)){printf("%d\n",i);return;}
}
int main(){
while(~scanf("%d%d",&n,&m)) solve();
}
Rng
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Avin is studying how to synthesize data. Given an integer n, he constructs an interval using the following method: he first generates a integer r between 1 and n (both inclusive) uniform-randomly, and then generates another integer l between 1 and r (both inclusive) uniform-randomly. The interval [l, r] is then constructed. Avin has constructed two intervals using the method above. He asks you what the probability that two intervals intersect is. You should print p* q(−1)(MOD 1, 000, 000, 007), while pq denoting the probability.
InputJust one line contains the number n (1 ≤ n ≤ 1, 000, 000).
OutputPrint the answer.
Sample Input
1 2
Sample Output
1 750000006
打表找规律
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
ll n;
ll qpow(ll base,ll n){
ll res=1;
while(n){
if(n&1) res=res*base%mod;
base=base*base%mod;
n>>=1;
}
return res%mod;
}
ll inv(ll b){return qpow(b,mod-2)%mod;}
void solve(){
ll fz,fm;
if(n%2) fm=n,fz=n/2+1;
else fm=n*2,fz=n+1;
printf("%lld\n",fz*inv(fm)%mod);
}
int main(){
while(~scanf("%lld",&n)) solve();
}
Budget
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Avin’s company has many ongoing projects with different budgets. His company records the budgets using numbers rounded to 3 digits after the decimal place. However, the company is updating the system and all budgets will be rounded to 2 digits after the decimal place. For example, 1.004 will be rounded down
to 1.00 while 1.995 will be rounded up to 2.00. Avin wants to know the difference of the total budget caused by the update.
InputThe first line contains an integer n (1 ≤ n ≤ 1, 000). The second line contains n decimals, and the i-th decimal ai (0 ≤ ai ≤ 1e18) represents the budget of the i -th project. All decimals are rounded to 3 digits.
OutputPrint the difference rounded to 3 digits..
Sample Input
1 1.001 1 0.999 2 1.001 0.999
Sample Output
-0.001 0.001 0.000
签到
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int z,x,n,m,w,h;
double r,t,ans;
char s[100];
int main()
{
while (~scanf("%d",&z))
{
ans=0;
for (int i=1;i<=z;i++)
{
scanf("%s",s);
for (int j=0;j<=strlen(s);j++)
if (s[j]=='.') x=j;
n=s[x+3]-'0';
if (n<=4) ans=ans-0.001*n;
else ans=ans+0.001*(10-n);
}
printf("%.3f\n",ans);
}
return 0;
}
Worker
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Avin meets a rich customer today. He will earn 1 million dollars if he can solve a hard problem. There are n warehouses and m workers. Any worker in the i-th warehouse can handle ai orders per day. The customer wonders whether there exists one worker assignment method satisfying that every warehouse handles the same number of orders every day. Note that each worker should be assigned to exactly one warehouse and no worker is lazy when working.
InputThe first line contains two integers n (1 ≤ n ≤ 1, 000), m (1 ≤ m ≤ 1018). The second line contains n integers. The i-th integer ai (1 ≤ ai ≤ 10) represents one worker in the i-th warehouse can handle ai orders per day.
OutputIf there is a feasible assignment method, print "Yes" in the first line. Then, in the second line, print n integers with the i-th integer representing the number of workers assigned to the i-th warehouse.
Otherwise, print "No" in one line. If there are multiple solutions, any solution is accepted.
Sample Input
2 6 1 2 2 5 1 2
Sample Output
Yes 4 2 No
签到
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;ll lc;
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
ll a[1050];
int main(){
ll m;
while(scanf("%lld%lld",&n,&m)!=EOF){
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(i==1) lc=a[i];
else lc=a[i]*lc/gcd(a[i],lc);
}
ll cnt=0;
for(int i=1;i<=n;i++){
cnt+=lc/a[i];
}
int fg=1;
if(cnt>m || m%cnt){
printf("No\n");
continue;
}
else{
ll ans=m/cnt;
printf("Yes\n");
for(int i=1;i<=n;i++){
if(i!=1) printf(" ");
printf("%lld",lc/a[i]*ans);
}
printf("\n");
}
}
return 0;
}
Class
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
Avin has two integers a, b (1 ≤ a, b ≤ 1, 000).
Given x = a + b and y = a - b, can you calculate a*b?
InputThe first line contains two integers x, y.
OutputPrint the result of a*b.
Sample Input
4 2
Sample Output
3
签到
#include <bits/stdc++.h>
using namespace std;
int main(){
int x,y;
while(scanf("%d%d",&x,&y)!=EOF){
printf("%d\n",(x+y)/2*(x-y)/2);
}
return 0;
}
