https://atcoder.jp/contests/abc371
C:
暴力。思路是把1-8的点映射到全排列上面,然后把有的点去掉没的点加上取ans最小值。
这题复杂度是\(8!\times7\times4\),暴力求全排列即可(第一次写暴力全排列思索了一会复杂度
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp make_pair
#define lowbit(x) ((x&(-x)))
#define int long long
const int maxn=2e5+10;
bool edgg[10][10];
bool edgh[10][10],vis[10];
int mp[10],n;
int a[10][10],sum=1e17;
void jud(){
int tmp=0;
//for(int i=1;i<=n;i++)cout<<mp[i]<<' ';
//cout<<endl;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(edgg[i][j]!=edgh[mp[i]][mp[j]]){
int x=mp[i],y=mp[j];if(x>y)swap(x,y);
tmp+=a[x][y];
}
}
}
sum=min(tmp,sum);
}
void dfs(int nw){
if(nw==n){
jud();return;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;mp[nw+1]=i;
dfs(nw+1);
vis[i]=0;
}
}
}
void solve(){
cin>>n;
int mg,mh,u,v;cin>>mg;
for(int i=1;i<=mg;i++){
cin>>u>>v;
edgg[u][v]=1;
edgg[v][u]=1;
}
cin>>mh;
for(int i=1;i<=mh;i++){
cin>>u>>v;
edgh[u][v]=1;
edgh[v][u]=1;
}
for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)cin>>a[i][j];
for(int i=1;i<=n;i++){
vis[i]=1;
mp[1]=i;dfs(1);
vis[i]=0;
}
cout<<sum<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int tt;tt=1;while(tt--){
solve();
}
}
D:
最先想到的是权值线段树。。但是发现只要二分找区间就能前缀和做了
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp make_pair
#define lowbit(x) ((x&(-x)))
#define int long long
const int maxn=2e5+10;
int x[maxn],p[maxn],pre[maxn];
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i];
}
for(int i=1;i<=n;i++){
cin>>p[i];pre[i]=pre[i-1]+p[i];
}
int q;cin>>q;
while(q--){
int ql,qr;cin>>ql>>qr;
int l=0,r=n,mid=(l+r+1)/2;
while(l<r){
if(x[mid]<ql)l=mid;
else r=mid-1;
mid=(l+r+1)/2;
}
int ml=mid,mr;
l=0,r=n,mid=(l+r+1)/2;
while(l<r){
if(x[mid]<=qr)l=mid;
else r=mid-1;
mid=(l+r+1)/2;
}
//cout<<pre[mid]<<' '<<pre[ml]<<"mk\n";
cout<<pre[mid]-pre[ml]<<"\n";
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int tt;tt=1;while(tt--){
solve();
}
}
标签:AtCoder,Beginner,10,int,cin,long,maxn,371,define
From: https://www.cnblogs.com/lyrrr/p/18414771