比赛链接
https://ac.nowcoder.com/acm/contest/1109?&headNav=www#question
B
设d[x]表示x到其最小生成树上父节点的距离。
则对于非树边x-y，如果d[y]=w(x,y)，就意味着从x到y也可以作为最小生成树的一部分。（这个判断可以用类似dijstra的方法实现）
考虑贪心构造答案，只要让一个点周围所有可能进入最小生成树的边都割断即可。
因此对于每个点，计算和它相连的可能进入最小生成树的边的个数，然后取一次最小值即可。
代码如下
/*
设d[x]表示x到其最小生成树上父节点的距离。
则对于非树边x-y，如果d[y]=w(x,y)，就意味着从x到y也可以作为最小生成树的一部分。（这个判断可以用类似dijstra的方法实现）
考虑贪心构造答案，只要让一个点周围所有可能进入最小生成树的边都割断即可。
因此对于每个点，计算和它相连的可能进入最小生成树的边的个数，然后取一次最小值即可。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<ll,int>pii;
const int maxn=50+5;
const int maxm=maxn*maxn;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n,m;
struct node{
int from,to;
ll w;
bool operator<(const node& h)const{return w<h.w;}
}edge[maxm<<1];
int head[maxn],tot;
void add(int from,int to,ll w){
edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to,edge[tot].w=w;
}
priority_queue<pii>q;
int deg[maxn],vis[maxn];
ll d[maxn];
void init(){
memset(head,0,sizeof(head));
tot=1;
memset(d,INF,sizeof(d));
memset(deg,0,sizeof(deg));
memset(vis,0,sizeof(vis));
while(q.size()) q.pop();
}
void dj(){
q.push(make_pair(0,1));
// d[1]=0;
while(q.size()){
pii now=q.top();q.pop();
int x=now.second;
// D(x);D(-now.first);E;
if(vis[x]) continue;
vis[x]=1;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
ll w=edge[i].w;
if(d[y]>w){
deg[y]=1;
d[y]=w;
q.push(make_pair(-d[y],y));
}
else if(d[y]==w) deg[y]++;
/*
if(d[y]>d[x]+w){
deg[y]=1,d[y]=d[x]+w;
q.push(make_pair(-d[y],y));
}
else if(d[y]==d[x]+w) deg[y]++;
*/
}
}
}
void solve(){
int ans=m+1;
// for(int i=1;i<=n;i++) D(deg[i]);
// E;
for(int i=1;i<=n;i++) ans=min(ans,deg[i]);
printf("%d\n",ans);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("Roads.in","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF){
init();
int from,to;
ll w;
for(int i=1;i<=m;i++) scanf("%d%d%lld",&from,&to,&w),add(from,to,w),add(to,from,w);
dj();
solve();
}
return 0;
}
C
对两个数组分别求线性基，然后对这两个线性基求交，答案就是
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50+5;
const int maxl=60+2;
const int INF=0x3f3f3f3f;
int n;
ll a[maxn],b[maxn],aa[3][maxl];
void init(){
memset(aa[0],0,sizeof(aa[0]));
memset(aa[1],0,sizeof(aa[1]));
memset(aa[2],0,sizeof(aa[2]));
}
inline void insert(ll x,int cur) {
for(int i=maxl-1; i>=0; --i) {
if(x>>i) {
if(!aa[cur][i]) {
aa[cur][i]=x;
break;
}
x^=aa[cur][i];
}
}
}
inline void Intersect(int x,int y) {
ll t1[maxl],t2[maxl];
for(int i=0; i<maxl; ++i) {
t1[i]=t2[i]=aa[x][i];
}
for(int i=0; i<maxl; ++i) {
if(aa[y][i]) {
ll x=aa[y][i],tp=0;
for(int j=maxl-1; j>=0; --j) {
if(x>>j) {
if(!t1[j]) {
t1[j]=x,t2[j]=tp;
break;
}
x^=t1[j],tp^=t2[j];
}
}
if(!x) insert(tp,2);
}
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Intersection.in","r",stdin);
while(cin>>n){
init();
for(int i=1;i<=n;i++) cin>>a[i],insert(a[i],0);
for(int i=1;i<=n;i++) cin>>b[i],insert(b[i],1);
// for(int i=0; i<maxl; ++i){
// D(i);D(aa[0][i]);D(aa[1][i]);E;
// }
Intersect(0,1);
// E;
/*
for(int i=0; i<maxl; ++i){
D(i);D(aa[2][i]);E;
}
E;
*/
ll ans=1;
for(int i=0; i<maxl; ++i){
if(aa[2][i]) ans*=2;
}
cout<<ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
E
将选择区间转化为选择区间的两个端点，因此首先对a数组求一遍前缀和。然后将这n+1个数（包括第0个数）排序，从两头开始向中间取数即可。（因为绝对值的存在，所以不用考虑顺序）
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int n,m;
ll C,a[maxn],b[maxn];
ll ans;
void init(){
ans=0;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Partial Sum.in","r",stdin);
while(scanf("%d%d%lld",&n,&m,&C)!=EOF){
init();
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1];
sort(a,a+n+1);
for(int i=0,j=n,cnt=1;i<j,cnt<=m;i++,j--,cnt++){
if(a[j]-a[i]<=C) break;
ans+=a[j]-a[i]-C;
}
printf("%lld\n",ans);
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
H
找出树的直径上的两个端点a和b（3遍dfs），然后将每个点和两个端点中较远的点连起来即可。
代码如下
/*
找出树的直径上的两个端点a和b（3遍dfs），然后将每个点和两个端点中较远的点连起来即可。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<ll,int>pii;
const int maxn=1e5+5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n,m;
struct node {
int from,to;
ll w;
} edge[maxn<<1];
queue<int>q;
int t,head[maxn],tot;
ll ans;
ll d1[maxn],d2[maxn];
void init(){
memset(head,0,sizeof(head));
tot=1;
}
void add(int u,int v,ll w) {
edge[++tot].to=v;edge[tot].from=head[u];edge[tot].w=w;head[u]=tot;
}
void dfs(int x,int fa,ll d){
d1[x]=d;
for(int i=head[x];i;i=edge[i].from){
int y=edge[i].to;
ll w=edge[i].w;
if(y==fa) continue;
dfs(y,x,d+w);
}
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Highway.in","r",stdin);
while(scanf("%d",&n)!=EOF){
init();
int from,to;
ll w;
for(int i=1;i<=n-1;i++) scanf("%d%d%lld",&from,&to,&w),add(from,to,w),add(to,from,w);
dfs(1,0,0);
int a=max_element(d1+1,d1+n+1)-d1;
// for(int i=1;i<=n;i++) D(d1[i]);
// E;
dfs(a,0,0);
int b=max_element(d1+1,d1+n+1)-d1;
// for(int i=1;i<=n;i++) D(d1[i]);
// E;
memcpy(d2,d1,sizeof(d1));
dfs(b,0,0);
// for(int i=1;i<=n;i++) D(d1[i]);
// E;
ans=-d1[a];
for(int i=1;i<=n;i++){
ans+=max(d1[i],d2[i]);
}
printf("%lld\n",ans);
}
return 0;
}
I
考虑一个性质，对于任意正整数n和m，总能找到。因此，为了让结果f(t)尽量小，就需要让i和j取到上式中的a和b。于是所求的答案就是这个数的中间值，即
如果觉得上面的话过于抽象，那么那样例具体解释下。
例如n=1，m=2时，lcm(n,m)=2。那么对于i、j，能取到的值就是0、1/2、1...
这之间最小的间距就是1/2，所以当t为1/4时，无论i和j怎么调整，答案都不会小于1/4。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5+5;
const int INF=0x3f3f3f3f;
ll n,m,a[maxn];
ll gcd(ll a,ll b){
return !b?a:gcd(b,a%b);
}
void solve(){
ll d=gcd(n,m);
ll lcm=n*m/d;
cout<<1<<"/"<<lcm*2<<endl;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Strange Optimization.in","r",stdin);
while(cin>>n>>m){
solve();
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
网友评论