2019ccpc江西省赛
A Cotree
题目链接
题意：给出n个点，仅有n-2条边，会形成两棵树，让你连一条边，求最小的。dis(i,j)代表对于i和j两个点路径上的边数。
思路：刚开始认为两颗树无论怎么连都不会影响答案。k队写了个树形DP+并查集，随便连了两天WA了。问了zl，发现肯定会影响。。zl得出连两颗树最为密集处，然后我尝试连了两棵树的重心，过了。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
long long ans = 0;
int son[maxn];
int n;
int f[maxn];
struct edge{
int to,next;
};
edge G[maxn<<1];
int head[maxn];
int edgeNum;
int mx,rt;
int Size;
int sz[maxn];
void add_edge(int a,int b)
{
G[edgeNum].to=b;
G[edgeNum].next=head[a];
head[a]=edgeNum++;
}
void dfsroot(int u,int fa){
sz[u]=1;
int num=0;
for(int i=head[u];i!=-1;i=G[i].next){
int v=G[i].to;
if(v==fa)
continue;
dfsroot(v,u);
sz[u]+=sz[v];
num=max(num,sz[v]);
}
num=max(num,Size-sz[u]);
if(num<mx){
mx=num;
rt=u;
}
}
void init() {
memset(head,-1,sizeof head);
for (int i = 1; i <= n; i++)f[i] = i;
}
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
void mix(int x, int y) {
int fx = find(x);
int fy = find(y);
f[fx] = fy;
}
void dfs(int x, int fa) {
//cout << x << endl;
son[x] = 1;
for(int i=head[x];i!=-1;i=G[i].next){
int y=G[i].to;
if (y == fa)continue;
dfs(y, x);
son[x] += son[y];
ans += 1ll * son[y] * (n - son[y]);
}
}
int main() {
scanf("%d", &n);
init();
for (int i = 1; i < n - 1; i++) {
int x, y;
scanf("%d%d", &x, &y);
add_edge(x,y);
add_edge(y,x);
mix(x, y);
}
int rt1 = find(1),rt2;
int tot=0;
for (int i = 1; i <= n; i++) {
int fi=find(i);
if (fi != rt1) {
tot++;
rt2=fi;
}
}
Size=n-tot;
mx=inf;
dfsroot(rt1,-1);
rt1=rt;
Size=tot;
mx=inf;
dfsroot(rt2,-1);
rt2=rt;
add_edge(rt1,rt2);
add_edge(rt2,rt1);
dfs(1, -1);
printf("%lld\n",ans);
}
C Trap
题目链接
题意：给定n条可能存在重复的边，在边中任取四条，要求构成等腰四边形，且四边形满足互质。
思路：预处理互质数的表，预处理出现次数，n^2枚举上下底边情况，再二分查找满足条件的斜边个数。等腰梯形满足条件，三遍大于第四条边。
#include <bits/stdc++.h>
#define maxn 10005
typedef long long ll;
using namespace std;
int n;
int num[maxn];
vector <int>a,b,v[maxn];
void input(){
int i,x;
for(i=0;i<n;i++)
{
scanf("%d",&x);
a.push_back(x);
num[x]++;
}
}
void solve(){
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());
for(int i=1;i<=10000;i++){
if(num[i]>=2){
b.push_back(i);
}
}
for(int i=1;i<=10000;i++){
for(int j=0;j<b.size();j++){
if(__gcd(i,b[j])==1){
v[i].push_back(b[j]);
}
}
}
ll ans=0;
for(int i=0;i<a.size();i++){
for(int j=i+1;j<a.size();j++){
int k=(a[j]-a[i])/2+1;
int GCD=__gcd(a[i],a[j]);
int pos=lower_bound(v[GCD].begin(),v[GCD].end(),k)-v[GCD].begin();
ans=ans+v[GCD].size()-pos;
if(GCD==1){
if(num[a[i]]==2&&a[i]>=k)ans--;
if(num[a[j]]==2&&a[j]>=k)ans--;
}
}
}
printf("%lld\n",ans);
}
int main(){
while(scanf("%d",&n)!=EOF){
a.clear();
b.clear();
for(int i=1;i<=10000;i++){
num[i]=0;
v[i].clear();
}
input();
solve();
}
} D Wave
题目链接
题意：对于给定数列，求一个数列满足，数列中至少两个元素，奇数位置都相同，偶数位置都相同，且奇数位置偶数位置值不同。求满足条件的最长子序列。
思路：想复杂了，k队的做法优化一下即可。枚举一个值作为奇数位置的值，将其之前的值省略，在奇数位置两两之间的的数都记录出现的次数。求最大出现次数即可。特判最后子序列长度为奇的情况。
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, c;
int a[maxn];
int num[105];
int vis[105];
int v[maxn];
int vcnt = 0;
void input() {
scanf("%d%d", &n, &c);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
}
void solve() {
int ans = 0;
int u=0;
int ANS;
for (int t = 1; t <= c; t++) {
int flag = 0;
int cnt = 0;
ans = 0;
memset(num, 0, sizeof num);
for (int i = 1; i <= n; i++) {
if (a[i] == t) {
flag = 1;
cnt++;
for (int j = 0; j < vcnt; j++) {
vis[v[j]] = 0;
}
vcnt = 0;
continue;
}
if (!flag)
continue;
if (!vis[a[i]]) {
num[a[i]]++;
vis[a[i]] = 1;
v[vcnt++] = a[i];
}
}
for (int i = 1; i <= c; i++) {
if (num[i] > ans)
{
ans = num[i];
u = i;
}
}
flag = 1;
//cout<<t <<' ' << ans << ' ' << u << endl;
for (int i = n; i >= 1; i--) {
if (a[i] == t)
break;
if (a[i] == u)
flag = 0;
}
ANS = max(ANS,2 * ans + flag);
//cout << ANS << endl;
}
printf("%d\n", ANS);
}
int main() {
input();
solve();
} F String
题目链接
题意：给出长度为n的序列,每次在n个字母中选择1个字母，求能构成avin字符串的几率
思路：水
#include <bits/stdc++.h>
#define maxn 105
typedef long long ll;
using namespace std;
char a[maxn];
int gcd(int x, int y){
int z = x % y;
while(z){
x = y;
y = z;
z = x % y;
}
return y;
}
int main(){
int n;
int num[4]={0};
while(scanf("%d",&n)!=EOF){
memset(num,0,sizeof num);
scanf("%s",a);
for(int i=0;i<strlen(a);i++){
if(a[i]=='a')
num[0]++;
else if(a[i]=='v')
num[1]++;
else if(a[i]=='i')
num[2]++;
else if(a[i]=='n')
num[3]++;
}
ll fm=pow(n,4);
ll fz=num[0]*num[1]*num[2]*num[3];
if(fz==0)
{
printf("0/1\n");
continue;
}
ll GCD=gcd(fm,fz);
fm=fm/GCD;
fz=fz/GCD;
printf("%lld/%lld\n",fz,fm);
}
return 0;
} G Traffic
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#include<unordered_map>
#define ll long long
#define maxn 100002
const int INF = 0x3f3f3f3f;
using namespace std;
int east[1002], north[1002];
int main(void){
int n, m, ans, i, flag;
while(scanf("%d %d",&m,&n)!=EOF){
ans = 0;
for(i = 0;i < m;i++){
scanf("%d",&east[i]);
}
for(i = 0;i < n;i++){
scanf("%d",&north[i]);
}
while(1){
flag = 1;
unordered_map<int,int> mp;
for(i = 0;i < m;i++){
mp[east[i]]++;
}
for(i = 0;i < n;i++){
mp[north[i] + ans]++;
}
unordered_map<int,int>::iterator iter;
for(iter = mp.begin();iter != mp.end();iter++){
if(iter->second > 1){
flag = 0;
break;
}
}
if(flag){
printf("%d\n",ans);
break;
}
ans++;
}
}
return 0;
} H Rng
题目链接
题意：对于[1,n]的区间先选择一个区间[l1,r1]，再选择一个区间[l2,r2]且满足r2<r1。求两个区间相交的概率
思路：概率打表找规律
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#define ll long long
#define maxn 100002
const int INF = 0x3f3f3f3f;
using namespace std;
const int mod = 1e9 + 7;
ll qpow(ll x,ll y){
ll res = 1;
while(y){
if(y & 1){
res = res * x % mod;
}
x = x * x % mod;
y >>= 1;
}
return res;
}
int main(void){
ll n;
while(scanf("%lld",&n)!=EOF){
printf("%lld\n",(n + 1) * n / 2 % mod * qpow(n * n % mod,mod - 2) % mod);
}
return 0;
} I Budget
题目链接
题意：给出n个数，求n个数四舍五入之后的赚或者亏了多少
思路：水
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#include<unordered_map>
#define ll long long
#define maxn 100002
const int INF = 0x3f3f3f3f;
using namespace std;
char ch[52];
int main(void){
int n, i, sum, len;
double ans;
while(scanf("%d",&n)!=EOF){
sum = 0;
for(i = 0;i < n;i++){
scanf("%s",ch);
len = strlen(ch);
if(ch[len - 1] >= '5'){
sum += 10 - ch[len - 1] + '0';
}
else{
sum -= ch[len - 1] - '0';
}
}
ans = sum / 1000.0;
printf("%.3f\n",ans);
}
return 0;
} J Worker
题目链接
题意：n个房间，有m个工作者，每个房间工作者工作ai时间，求一种分配方案使得每个房间工作者工作时间总和相同。
思路：求最小公倍数,题目中1018应该是1e18，需开long long
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#define ll long long
#define maxn 100002
const int INF = 0x3f3f3f3f;
using namespace std;
ll gcd(ll x, ll y){
ll z = x % y;
while(z){
x = y;
y = z;
z = x % y;
}
return y;
}
ll lcm(ll x, ll y){
return x / gcd(x,y) * y;
}
ll num[1202];
int main(void){
ll n, m, i, temp, sum;
while(scanf("%lld %lld",&n,&m)!=EOF){
for(i = 0;i < n;i++){
scanf("%lld",&num[i]);
}
if(n == 1){
puts("Yes");
printf("%lld\n",m);
}
else{
temp = lcm(num[0],num[1]);
for(i = 2;i < n;i++){
temp = lcm(temp,num[i]);
}
sum = 0;
for(i = 0;i < n;i++){
sum += temp / num[i];
}
if(m % sum){
puts("No");
}
else{
puts("Yes");
for(i = 0;i < n;i++){
if(i){
printf(" ");
}
printf("%lld",temp / num[i] * m / sum);
}
puts("");
}
}
}
return 0;
} K Class
#include<bits/stdc++.h>
using namespace std;
const int maxn = 7e3 + 5;
int main() {
int x, y;
scanf("%d%d", &x, &y);
int a = (x + y) / 2;
int b = a - y;
cout << a * b << endl;
}
京公网安备 11010502036488号