科林明伦杯 哈尔滨理工大学第十届程序设计竞赛 题解
点对最大值
思路：对于每个点求出向下延伸最大的两条仅带一个端点的链，并通过两条链之和更新最大值。因为每个节点也有值，因此节点的值也算该节点向下延伸且只有一个端点的链。初始每个节点向下最大链为本节点，并通过子节点的最大链不断更新自己向下链的最大值。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 1000005
#define INF 0x3f3f3f3f
int head[N],dp[N];
int tot,ans;
struct
{
int to,next,v;
} edge[N*2];
void addedge(int from,int to,int v)
{
edge[tot].to=to;
edge[tot].next=head[from];
edge[tot].v=v;
head[from]=tot++;
}
void dfs(int x,int pre)
{
int ma[2];
ma[0]=dp[x];
ma[1]=-INF;
int zt=0;
for(int i=head[x]; i!=-1; i=edge[i].next)
{
if(edge[i].to==pre)
continue;
dfs(edge[i].to,x);
ma[1]=max(ma[1],dp[edge[i].to]+edge[i].v);
if(ma[0]<ma[1])
swap(ma[0],ma[1]);
zt=1;
}
if(zt)
ans=max(ans,ma[0]+ma[1]);
dp[x]=ma[0];
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
scanf("%d",&t);
while(t--)
{
tot=0;
ans=-INF;
memset(head,-1,sizeof(head));
int n;
scanf("%d",&n);
int fa,v;
for(int i=2; i<=n; i++)
{
scanf("%d %d",&fa,&v);
addedge(fa,i,v);
addedge(i,fa,v);
}
for(int i=1; i<=n; i++)
{
scanf("%d",&dp[i]);
}
dfs(1,-1);
printf("%d\n",ans);
}
}
减成一
思路：由于每次操作可以将一个区间内的数减一。如下图所示，通过计算出差分数组，操作可以转为先选取一个数减一再选取一个数加一。目标的差分数组也就变成了第一个数为1，其余为0的数组。因此，最快操作方式就是将差分数组第一个数减为1，其余减为0。即操作数为差分数组的正数之和减一。
#include<stdio.h>
#define N 100005
long long f[N],a[N];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
long long t;
scanf("%lld",&t);
long long num=0;
while(t--)
{
long long n;
scanf("%lld",&n);
num+=n;
long long sum=0;
for(long long i=0;i<n;i++)
{
scanf("%lld",&a[i]);
if(i)
f[i]=a[i]-a[i-1];
else
f[i]=a[i];
if(f[i]>0)
sum+=f[i];
}
printf("%lld\n",sum-1);
}
}
面积
思路：中间为一个正方形，四边为半圆，面积为x*x+2*pi*(x/2)*(x/2)
#include<stdio.h>
#include<algorithm>
double pi=3.14;
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
scanf("%d",&t);
while(t--)
{
double x;
scanf("%lf",&x);
double ans = 1.0*x*x+2.0*pi*(x/2.0)*(x/2.0);
printf("%.2f\n",ans);
}
}
扔硬币
思路：由于已知部分硬币的方向。因此，扔n个硬币的情况要在2的n次幂的中去掉少于m个硬币是反面的情况。
对于k+m>n是不可能的，直接输出0.
其余情况：C(n,k)/[ 2^n - ∑(C(n,i)) ] (i<m)
由于数据量较大，需要进行预处理等。
#include<stdio.h>
#define N 100005
#define M 1000000007
long long f[N],finv[N],inv[N];
long long cnm(long long n,long long m)
{
return ((f[n]*finv[m]%M)*finv[n-m])%M;
}
long long km(long long x,long long y)
{
long long sum=1;
while(y)
{
if(y&1)
sum=(sum*x)%M;
y/=2;
x=(x*x)%M;
}
return sum;
}
void init()
{
f[0]=inv[0]=finv[0]=1;
f[1]=inv[1]=finv[1]=1;
for(long long i=2;i<=100000;i++)
{
f[i]=f[i-1]*i%M;
inv[i]=(M-M/i)*inv[M%i]%M;
finv[i]=(finv[i-1]*inv[i])%M;
}
}
int main()
{
//freopen("C.in.txt","r",stdin);
//freopen("C.out.txt","w",stdout);
init();
int t;
scanf("%d",&t);
while(t--)
{
long long n,m,k;
scanf("%lld %lld %lld",&n,&m,&k);
if(m+k>n)
printf("0\n");
else
{
long long sum=0;
for(long long i=0; i<m; i++)
sum=(sum+cnm(n,i))%M;
sum=(km(2,n)-sum+M)%M;
sum=cnm(n,k)*km(sum,M-2)%M;
printf("%lld\n",sum);
}
}
}
/*
1
3 1 1
428571432
3/(2^3-1)
*/
赛马
思路：
每次暴力寻找比b[i]大且没参赛过的最小a[j]值（1<=i<=n，1<=j<=n）。时间复杂度O(n^2)。
将a[i]和b[i]数组放到一起排序，每次按照最大括号匹配的方式计算。时间复杂度O(nlogn)。
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 1005
int a[N],b[N];
bool vis[N];
struct s
{
int tp,v;
}f[N*2];
bool cmp(s aa,s bb)
{
if(aa.v==bb.v)
{
return aa.tp<bb.tp;
}
return aa.v<bb.v;
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
// n^2
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
vis[i]=true;
}
sort(a+1,a+n+1);
int ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
int zt=1,id=-1;
for(int j=1;j<=n;j++)
{
if(a[j]>b[i]&&vis[j])
{
zt=0;
vis[j]=false;
ans++;
break;
}
else if(vis[j]&&id==-1)
{
id=j;
}
}
if(zt)
{
vis[id]=false;
}
}
printf("%d\n",ans);
// nlogn
// for(int i=1;i<=n;i++)
// {
// f[i].tp=1;
// scanf("%d",&f[i].v);
// }
// for(int i=1;i<=n;i++)
// {
// f[n+i].tp=2;
// scanf("%d",&f[n+i].v);
// }
// sort(f+1,f+n*2+1,cmp);
// int num=0,ans=0;
// for(int i=1;i<=2*n;i++)
// {
// if(f[i].tp==2)
// num++;
// else if(num>0)
// {
// num--;
// ans++;
// }
// }
// printf("%d\n",ans);
}
}
三角形
思路：三角形两边之和大于第三边，因此不构成三角形的条件就是存在两边之和不超过另一边。所以按照斐波那契数列的方法切割可以使得切割的段数最大，1，1，2，3，5这样可以使得任意三根木棒不能组成三角形，最后无法切割的部分组成一根长的木棒。
#include <bits/stdc++.h>
using namespace std;
unsigned long long a[105];
unsigned long long b[105];
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
a[1] = 1; a[2] = 2;
unsigned long long b = 1, c = 1;
for(int i = 3; i <= 91; ++i) {
a[i] = a[i - 1] + b + c;
b = c; c = a[i] - a[i - 1];
// printf("%llu\n", a[i]);
}
int T;
scanf("%d", &T);
while(T--) {
unsigned long long n;
scanf("%llu", &n);
if (n == 0) {
printf("0\n");
continue;
}
int ans = 0;
for(int i = 1; i <= 91; ++i) {
if(a[i] <= n) ans = i;
}
printf("%d\n", ans);
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
养花
思路：采用网络流直接进行建图，对于四种操作每次都新建两个点from和to，题面中的[a1,a2]区间每个节点连接到from节点，to连接[b1,b2]区间的每个节点。然后跑最大流即可。
但对于区间的最大流还可采用线段树建图的方式，建立两棵线段树，每种操作新建节点时直接在两棵线段树上所对应的区间即可。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Edge{
int next,to,f;
};
struct Dinic
{
int s,t;
Edge e[4000010];
int cnt=2,head[4000010]={0};
int dis[4000010]={0};
Dinic (){}
void init(int _s,int _t)
{
cnt=2;
s=_s,t=_t;
memset(head,0,sizeof(head));
}
void addedge(int u,int v,int f)
{
e[cnt]={head[u],v,f};
head[u]=cnt++;
e[cnt]={head[v],u,0};
head[v]=cnt++;
}
bool bfs()
{
memset(dis,0,sizeof(dis));
dis[s]=1;
queue<int> q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(!dis[v]&&e[i].f>0)
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return dis[t]!=0;
}
int dfs(int u,int flow)
{
if(u==t||flow==0) return flow;
int flow_sum=0;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to,f=e[i].f;
if(dis[v]!=dis[u]+1||f==0) continue;
int temp=dfs(v,min(flow-flow_sum,f));
e[i].f-=temp;
e[i^1].f+=temp;
flow_sum+=temp;
if(flow_sum>=flow) break;
}
if(!flow_sum) dis[u]=-1;
return flow_sum;
}
int maxflow()
{
int ans=0;
while(bfs())
{
while(int temp=dfs(s,0x7fffffff)) {
ans+=temp;
}
}
return ans;
}
}DC;
struct Node {
int l, r;
Node(): l(0), r(0) {}
}T[4000010];
int tot, rt1, rt2;
int n, m, k;
int h[10007];
void build(int &r1, int &r2, int l, int r)
{
r1 = ++tot;
r2 = (l == r ? r1: ++tot);
if(l == r) {
// if(l == 1) DC.addedge(DC.s, r1, n);
if(l == k) DC.addedge(r1, DC.t, n);
else DC.addedge(DC.s, r1, h[l]);
return ;
}
int mid = (l + r) >> 1;
build(T[r1].l, T[r2].l, l, mid);
build(T[r1].r, T[r2].r, mid + 1, r);
DC.addedge(r1, T[r1].l, INF);
DC.addedge(r1, T[r1].r, INF);
DC.addedge(T[r2].l, r2, INF);
DC.addedge(T[r2].r, r2, INF);
}
void query(int rt, int l, int r, int L, int R, int p, int id)
{
if(!rt || l > R || r < L) return;
if(L <= l && r <= R) {
if (id == 0) DC.addedge(p, rt, INF);
else DC.addedge(rt, p, INF);
return ;
}
int mid = (l + r) >> 1;
query(T[rt].l, l, mid, L, R, p, id);
query(T[rt].r, mid + 1, r, L, R, p, id);
}
int main()
{
freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d", &n, &m, &k);
DC.init(1, 2);
tot = 2;
rt1 = rt2 = 0;
for (int i = 1; i <= k; ++i)
h[i] = 0;
for (int i = 1; i <= n; ++i) {
int as;
scanf("%d", &as);
h[as]++;
}
build(rt1, rt2, 1, k);
for(int i = 1; i <= m; ++i) {
int op, num;
scanf("%d%d", &op, &num);
int l1, l2, r1, r2;
if (op == 1) {
scanf("%d%d", &l1, &l2);
r1 = l1; r2 = l2;
}
if (op == 2) {
scanf("%d%d%d", &l1, &r1, &l2);
r2 = l2;
}
if (op == 3) {
scanf("%d%d%d", &l1, &l2, &r2);
r1 = l1;
}
if (op == 4) {
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
}
if(l1<1||l2<1||r1<1||r2<1||l1>k||l2>k||r1>k||r2>k)
printf("NO\n");
int from = ++tot;
int to = ++tot;
DC.addedge(from, to, num);
query(rt1, 1, k, l2, r2, to, 0);
query(rt2, 1, k, l1, r1, from, 1);
}
// printf("%d\n", DC.maxflow());
}
fclose(stdin);
fclose(stdout);
return 0;
}
/*
5 4 5
1 1 1 1 1
1 3 1 3
1 3 3 2
1 3 2 5
4 1 1 1 4 5
*/
直线
思路：平面中直线交点最多n*(n-1)/2个，需要大数乘法。因为公式中(n-1)和除2操作可以直接在unsigned long long中完成，只需要采用大数乘，或其他方法。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
#define MAXN 9999
#define MAXSIZE 1010
#define DLEN 4
class BigNum
{
private:
int a[500]; //可以控制大数的位数
int len;
public:
BigNum(){len=1;memset(a,0,sizeof(a));} //构造函数
BigNum(const int); //将一个int类型的变量转化成大数
BigNum(const char*); //将一个字符串类型的变量转化为大数
BigNum(const BigNum &); //拷贝构造函数
BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算
friend istream& operator>>(istream&,BigNum&); //重载输入运算符
friend ostream& operator<<(ostream&,BigNum&); //重载输出运算符
BigNum operator+(const BigNum &)const; //重载加法运算符，两个大数之间的相加运算
BigNum operator-(const BigNum &)const; //重载减法运算符，两个大数之间的相减运算
BigNum operator*(const BigNum &)const; //重载乘法运算符，两个大数之间的相乘运算
BigNum operator/(const int &)const; //重载除法运算符，大数对一个整数进行相除运算
BigNum operator^(const int &)const; //大数的n次方运算
int operator%(const int &)const; //大数对一个int类型的变量进行取模运算
bool operator>(const BigNum &T)const; //大数和另一个大数的大小比较
bool operator>(const int &t)const; //大数和一个int类型的变量的大小比较
void print(); //输出大数
};
BigNum::BigNum(const int b) //将一个int类型的变量转化为大数
{
int c,d=b;
len=0;
memset(a,0,sizeof(a));
while(d>MAXN)
{
c=d-(d/(MAXN+1))*(MAXN+1);
d=d/(MAXN+1);
a[len++]=c;
}
a[len++]=d;
}
BigNum::BigNum(const char *s) //将一个字符串类型的变量转化为大数
{
int t,k,index,L,i;
memset(a,0,sizeof(a));
L=strlen(s);
len=L/DLEN;
if(L%DLEN)len++;
index=0;
for(i=L-1;i>=0;i-=DLEN)
{
t=0;
k=i-DLEN+1;
if(k<0)k=0;
for(int j=k;j<=i;j++)
t=t*10+s[j]-'0';
a[index++]=t;
}
}
BigNum::BigNum(const BigNum &T):len(T.len) //拷贝构造函数
{
int i;
memset(a,0,sizeof(a));
for(i=0;i<len;i++)
a[i]=T.a[i];
}
BigNum & BigNum::operator=(const BigNum &n) //重载赋值运算符，大数之间赋值运算
{
int i;
len=n.len;
memset(a,0,sizeof(a));
for(i=0;i<len;i++)
a[i]=n.a[i];
return *this;
}
istream& operator>>(istream &in,BigNum &b)
{
char ch[MAXSIZE*4];
int i=-1;
in>>ch;
int L=strlen(ch);
int count=0,sum=0;
for(i=L-1;i>=0;)
{
sum=0;
int t=1;
for(int j=0;j<4&&i>=0;j++,i--,t*=10)
{
sum+=(ch[i]-'0')*t;
}
b.a[count]=sum;
count++;
}
b.len=count++;
return in;
}
ostream& operator<<(ostream& out,BigNum& b) //重载输出运算符
{
int i;
cout<<b.a[b.len-1];
for(i=b.len-2;i>=0;i--)
{
printf("%04d",b.a[i]);
}
return out;
}
BigNum BigNum::operator+(const BigNum &T)const //两个大数之间的相加运算
{
BigNum t(*this);
int i,big;
big=T.len>len?T.len:len;
for(i=0;i<big;i++)
{
t.a[i]+=T.a[i];
if(t.a[i]>MAXN)
{
t.a[i+1]++;
t.a[i]-=MAXN+1;
}
}
if(t.a[big]!=0)
t.len=big+1;
else t.len=big;
return t;
}
BigNum BigNum::operator-(const BigNum &T)const //两个大数之间的相减运算
{
int i,j,big;
bool flag;
BigNum t1,t2;
if(*this>T)
{
t1=*this;
t2=T;
flag=0;
}
else
{
t1=T;
t2=*this;
flag=1;
}
big=t1.len;
for(i=0;i<big;i++)
{
if(t1.a[i]<t2.a[i])
{
j=i+1;
while(t1.a[j]==0)
j++;
t1.a[j--]--;
while(j>i)
t1.a[j--]+=MAXN;
t1.a[i]+=MAXN+1-t2.a[i];
}
else t1.a[i]-=t2.a[i];
}
t1.len=big;
while(t1.a[len-1]==0 && t1.len>1)
{
t1.len--;
big--;
}
if(flag)
t1.a[big-1]=0-t1.a[big-1];
return t1;
}
BigNum BigNum::operator*(const BigNum &T)const //两个大数之间的相乘
{
BigNum ret;
int i,j,up;
int temp,temp1;
for(i=0;i<len;i++)
{
up=0;
for(j=0;j<T.len;j++)
{
temp=a[i]*T.a[j]+ret.a[i+j]+up;
if(temp>MAXN)
{
temp1=temp-temp/(MAXN+1)*(MAXN+1);
up=temp/(MAXN+1);
ret.a[i+j]=temp1;
}
else
{
up=0;
ret.a[i+j]=temp;
}
}
if(up!=0)
ret.a[i+j]=up;
}
ret.len=i+j;
while(ret.a[ret.len-1]==0 && ret.len>1)ret.len--;
return ret;
}
BigNum BigNum::operator/(const int &b)const //大数对一个整数进行相除运算
{
BigNum ret;
int i,down=0;
for(i=len-1;i>=0;i--)
{
ret.a[i]=(a[i]+down*(MAXN+1))/b;
down=a[i]+down*(MAXN+1)-ret.a[i]*b;
}
ret.len=len;
while(ret.a[ret.len-1]==0 && ret.len>1)
ret.len--;
return ret;
}
int BigNum::operator%(const int &b)const //大数对一个 int类型的变量进行取模
{
int i,d=0;
for(i=len-1;i>=0;i--)
d=((d*(MAXN+1))%b+a[i])%b;
return d;
}
BigNum BigNum::operator^(const int &n)const //大数的n次方运算
{
BigNum t,ret(1);
int i;
if(n<0)exit(-1);
if(n==0)return 1;
if(n==1)return *this;
int m=n;
while(m>1)
{
t=*this;
for(i=1;(i<<1)<=m;i<<=1)
t=t*t;
m-=i;
ret=ret*t;
if(m==1)ret=ret*(*this);
}
return ret;
}
bool BigNum::operator>(const BigNum &T)const //大数和另一个大数的大小比较
{
int ln;
if(len>T.len)return true;
else if(len==T.len)
{
ln=len-1;
while(a[ln]==T.a[ln]&&ln>=0)
ln--;
if(ln>=0 && a[ln]>T.a[ln])
return true;
else
return false;
}
else
return false;
}
bool BigNum::operator>(const int &t)const //大数和一个int类型的变量的大小比较
{
BigNum b(t);
return *this>b;
}
void BigNum::print() //输出大数
{
int i;
printf("%d",a[len-1]);
for(i=len-2;i>=0;i--)
printf("%04d",a[i]);
printf("\n");
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int T;
scanf("%d", &T);
while(T--) {
string n;
cin >> n;
BigNum a(n.c_str());
a = a * (a - 1) / 2;
a.print();
}
// fclose(stdout);
// fclose(stdin);
return 0;
}
字典序
思路：对于a[i]位置的数据分一下三种情况进行讨论
若a[i] == a[i+1]，那么删除a[i]后与删除a[i + 1]的结果一样，那么a[i]出处的字典序会比a[i+1]出小
若a[i] < a[i+1]，那么删除a[i]后的数组在第i位上比删除a[i+1]所得到的更大，所以第i个位置的字典序比后面位置的字典序都小
若a[i] > a[i+1]，那么删除a[i]后的数组在第i位上比删除a[i+1]所得到的更小，所以第i个位置的字典序比后面位置的字典序都大。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
int a[maxn];
int L[maxn], R[maxn];
int cnt;
deque<int> d;
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int T;
scanf("%d", &T);
while(T--) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
cnt = 0;
for (int i = 1; i <= n; ++i) {
int j = i;
while(a[j + 1] == a[j] && j < n) j++;
a[++cnt] = a[i]; L[cnt] = i; R[cnt] = j;
i = j;
}
a[cnt + 1] = 0;
d.clear();
for (int i = cnt; i > 0; --i) {
if(a[i] > a[i + 1]) d.push_front(i);
else d.push_back(i);
}
bool ok = true;
for(auto i : d) {
for (int j = L[i]; j <= R[i]; ++j) {
if(!ok) printf(" ");
printf("%d", j);
ok = false;
}
}
puts("");
}
fclose(stdin);
fclose(stdout);
return 0;
}
/*
3
5
699 713 941 972 451
5
2 3 4 5 1
2 4 5 3 1
*/
最大值
思路：对字符串求next数组，kmp中next数组表示的是前i个位置构成的字符串的前缀和后缀最大的匹配数。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
char a[maxn];
int Next[maxn];
int len;
void getNext()
{
int j=0,k=-1;
Next[0]=-1;
while(j<len){
if(k==-1||a[j]==a[k])Next[++j]=++k;
else k=Next[k];
}
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int T;
scanf("%d", &T);
while(T--){
scanf("%s", a);
len = strlen(a);
getNext();
int ans = 0;
for (int i = 1; i <= len; ++i)
ans = max(ans, Next[i]);
printf("%d\n", ans);
}
// fclose(stdin);
// fclose(stdout);
return 0;
}