一道图论神题
(god)
Time Limit:1000ms Memory Limit:128MB
题目描述
LYK有一张无向图G={V,E}，这张无向图有n个点m条边组成。并且这是一张带权图，只有点权。
LYK想把这个图删干净，它的方法是这样的。每次选择一个点，将它删掉，但删这个点是需要代价的。假设与这个点相连的还没被删掉的点是u1,u2,…,uk。LYK将会增加a[u1],a[u2],…,a[uk]的疲劳值。
它想将所有点都删掉，并且删完后自己的疲劳值之和最小。你能帮帮它吗？
输入格式(god.in)
第一行两个数n,m表示一张n个点m条边的图。
第二行n个数ai表示点权。
接下来m行每行三个数u,v，表示有一条连接u,v的边。数据保证任意两个点之间最多一条边相连，并且不存在自环。
输出格式(god.out)
你需要输出这个最小疲劳值是多少。
输入样例
4 3
10 20 30 40
1 4
1 2
2 3
输出样例
40
样例解释
一个合理的方法是先删4号点，此时有10点疲劳值。接下来删3号点，获得20点疲劳值，再删2号点，获得10点疲劳值，最后删1号点，没有疲劳值。总计40点疲劳值。
对于30%的数据n<=10。
对于60%的数据n,m<=1000。
对于100%的数据1<=n,m,ai<=100000
/*
贪心
每次选择权值最大的点删除即可
*/
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define maxn 100010
int n,m,head[maxn],w[maxn];
struct node{
int to,pre,v;
}e[maxn*];
struct Node{
int id,val;
bool operator < (const Node b)const{
return val<b.val;
}
};
priority_queue<Node>q;
int qread(){
int i=;
char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}
return i;
}
void Insert(int from,int to,int v,int num){
e[num].to=to;
e[num].pre=head[from];
e[num].v=v;
head[from]=num;
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("god.in","r",stdin);freopen("god.out","w",stdout);
n=qread();m=qread();
Node now;
for(int i=;i<=n;i++){
w[i]=qread();
now.id=i;now.val=w[i];
q.push(now);
}
int x,y;
for(int i=;i<=m;i++){
x=qread();y=qread();
Insert(x,y,w[y],i);Insert(y,x,w[x],i+m);
}
long long ans=;
while(!q.empty()){
now=q.top();q.pop();
int cur=now.id;
for(int i=head[cur];i;i=e[i].pre){
ans+=e[i].v;
if(i<=m)e[i].v=,e[i+m].v=;
if(i>m)e[i].v=,e[i-m].v=;
}
}
cout<<ans;
fclose(stdin);fclose(stdout);
return ;
}
100分 贪心
位运算2
(bit)
Time Limit:1000ms Memory Limit:128MB
题目描述
LYK拥有一个十进制的数N。它赋予了N一个新的意义：不考虑N的符号，将N每一位都拆开来后再加起来就是N所拥有的价值。例如数字123拥有6的价值，数字999拥有27的价值，数字-233拥有8的价值。
假设数字N的价值是K，LYK想找到一个价值是K+1的数字，当然这个答案实在太多了，LYK想使得这个价值为K+1的数字尽可能大，并且需要保证这个数字小于N。
输入格式(bit.in)
一个整数N。
输出格式(bit.out)
一个数表示答案。你需要输出一个整数，且这个数不包含前导0。
输入样例1
199
输出样例1
-299
输入样例2
1520
输出样例2
1512
对于20%的数据|N|<=10
对于40%的数据|N|<=100
对于60%的数据|N|<=10^9
对于80%的数据|N|<=10^1000
对于100%的数据|N|<=10^100000。
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100010
using namespace std;
int bit[maxn],len,f[maxn],w;
char s[maxn];
bool flag=;
void dfs(int pos,bool limit,int sum){
if(flag)return;
if(sum>w)return;
if(pos==len+){
if(sum==w){
int start=;
while(f[start]==)start++;
for(int i=start;i<=len;i++)printf("%d",f[i]);
flag=;
}
return;
}
if(limit){
for(int i=bit[pos];i>=;i--){
f[pos]=i;
dfs(pos+,limit&&(i==bit[pos]),sum+i);
}
}
else{
for(int i=;i>=;i--){
f[pos]=i;
dfs(pos+,,sum+i);
}
}
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("bit.in","r",stdin);freopen("bit.out","w",stdout);
scanf("%s",s+);
len=strlen(s+);
if(s[]<=''&&s[]>='')for(int i=;i<=len;i++)bit[i]=s[i]-'';
else {
for(int i=;i<=len;i++)bit[i]=s[i]-'';
bit[]=-;
}
if(bit[]!=-){//n是正数
if(bit[len]<=&&bit[len-]>){
bit[len]+=;
bit[len-]--;
for(int i=;i<=len;i++)printf("%d",bit[i]);
return ;
}
for(int i=;i<=len;i++)w+=bit[i];
w++;
dfs(,,);
if(flag)return ;
int cnt=;
while(w){
if(w>=){
f[++cnt]=;
w-=;
}
else f[++cnt]=w,w=;
}
printf("-");
for(int i=cnt;i>=;i--)printf("%d",f[i]);
}
if(bit[]==-){//n是负数
int now=len;
while(now>&&bit[now]==)now--;
if(bit[now]!=){
bit[now]++;
printf("-");
for(int i=;i<=len;i++)printf("%d",bit[i]);
return ;
}
else{
printf("-1");
for(int i=;i<=len;i++)printf("%d",bit[i]);
return ;
}
}
}
80分 暴力
/*
全程特判：
1.最后一位<8，倒数第二位>0，最后一位+2，倒数第二位-1
2.6368899->6359999
3.4566544099->4566543992
从后往前，统计9-a[i]的和，直到>=2。
再往前，找第一个>0的数，把这个数-1， 再整理下后面的数（一开始全是9...，尽可能大）
*/
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
char s[];
int len,sum,i,j,FLAG;
int main()
{
freopen("bit.in","r",stdin);
freopen("bit.out","w",stdout);
scanf("%s",s); FLAG=;
if (s[]!='-')
{
len=strlen(s); sum=;
for (i=len-; i>=; i--)
{
if (s[i]>='' && sum>=)
{
s[i]=char(s[i]-);
sum=;
for (j=i+; j<len; j++)
{
while (sum && s[j]<'')
{
sum--;
s[j]=char(s[j]+);
}
}
int SS=;
for (j=i+; j<len; j++) SS+=s[j]-'';
for (j=i+; j<len; j++)
{
if (SS>=) {s[j]=''; SS-=;} else {s[j]=char(SS+''); SS=;}
}
FLAG=;
break;
}
sum+=''-s[i];
}
if (FLAG)
{
for (i=; i<len; i++) if (s[i]!='') break;
for (j=min(len-,i); j<len; j++) cout<<s[j]; cout<<endl;
return ;
}
cout<<'-';
for (i=len-; i>=; i--)
{
if (s[i]<'')
{
s[i]=char(s[i]+);
FLAG=;
break;
}
}
if (FLAG)
{
for (i=; i<len; i++) if (s[i]!='') break;
for (j=min(len-,i); j<len; j++) cout<<s[j]; cout<<endl;
return ;
}
cout<<;
for (i=; i<len; i++) if (s[i]!='') break;
for (j=min(len-,i); j<len; j++) cout<<s[j]; cout<<endl;
return ;
} FLAG=;
cout<<'-';
len=strlen(s);
for (i=len-; i>=; i--)
{
if (s[i]<'')
{
s[i]=char(s[i]+);
FLAG=;
break;
}
}
if (FLAG)
{
for (i=; i<len; i++) if (s[i]!='') break;
for (j=min(len-,i); j<len; j++) cout<<s[j]; cout<<endl;
return ;
}
cout<<;
for (i=; i<len; i++) if (s[i]!='') break;
for (j=min(len-,i); j<len; j++) cout<<s[j]; cout<<endl;
return ;
}
100分
逆序对
(pair)
Time Limit:1000ms Memory Limit:128MB
题目描述
LYK最近在研究逆序对。
这个问题是这样的。
一开始LYK有一个2^n长度的数组ai。
LYK有Q次操作，每次操作都有一个参数k。表示每连续2^k长度作为一个小组。假设n=4,k=2，则a[1],a[2],a[3],a[4]为一个小组，a[5],a[6],a[7],a[8]为一个小组，a[9],a[10],a[11],a[12]为一个小组，a[13],a[14],a[15],a[16]也为一个小组。
然后LYK对于每个小组都翻转，也就是说原数组会变成a[4],a[3],a[2],a[1],a[8],a[7],a[6],a[5],a[12],a[11],a[10],a[9],a[16],a[15],a[14],a[13]。之后它想求出这2^n个数的逆序对是多少。
因此你需要输出对于每次操作，操作完后这2^n个数的逆序对有多少对。
两个数ai,aj被称为逆序对当且仅当i<j且ai>aj。
输入格式(pair.in)
第一行一个数n。
接下来一行2^n个数ai表示一开始的数组。
接下来一行一个数Q，表示操作的次数。
接下来一行Q个数，表示每次操作的参数k。
输出格式(pair.out)
Q行，表示每次操作后的答案。
输入样例
2
2 1 4 3
4
1 2 0 2
输出样例
0
6
6
0
样例解释
第一次操作，{2,1,4,3}->{1,2,3,4}
第二次操作，{1,2,3,4}->{4,3,2,1}
第三次操作，{4,3,2,1}->{4,3,2,1}
第四次操作，{4,3,2,1}->{1,2,3,4}
对于30%的数据n<=10，Q<=10。
对于50%的数据n<=10，Q<=1000。
对于80%的数据n<=10，Q<=200000。
对于100%的数据n<=17，Q<=200000，1<=ai<=2^n。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 131073
int n,a[][maxn],Q,tr[maxn];
long long ans;
int qread(){
int i=;
char ch=getchar();
while(ch<''||ch>'')ch=getchar();
while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}
return i;
}
long long query(int pos){
long long res=;
while(pos){
res+=tr[pos];
pos-=pos&(-pos);
}
return res;
}
void add(int pos,int v){
while(pos<=(<<n)){
tr[pos]++;
pos+=pos&(-pos);
}
}
int main(){
//freopen("Cola.txt","r",stdin);
//freopen("pair.in","r",stdin);freopen("pair.out","w",stdout);
n=qread();
for(int i=;i<=(<<n);i++)a[][i]=qread();
Q=qread();
int x;
for(int i=;i<=Q;i++){
memset(tr,,sizeof(tr));
x=qread();x=(<<x);
for(int j=;j<=(<<n);j+=x)//区间反转
for(int cnt=,k=j,l=j+x-;cnt<=x;cnt++,k++,l--)
a[i&][k]=a[(i-)&][l];
ans=;
for(int j=;j<=(<<n);j++){
ans+=j--query(a[i&][j]);
add(a[i&][j],);
}
cout<<ans<<endl;
}
fclose(stdin);fclose(stdout);
return ;
}
树状数组（考场代码）
/*
12345678 [1,4][5,8]
56781234 [1,2][3,4] [5,6][7,8]
78563412 [1,1][2,2] [3,3][4,4] [5,5][6,6] [7,7][8,8]
87654321 k=4 -> 把一个对k的翻转操作 转变成对k,k-1,k-2,...,1的平移操作
平移操作对答案有什么影响
对3进行平移，[1,4][5,8] -> [5,8][1,4] 对于所有8个数为一组，答案=逆序对个数的最大值-当前答案 1,2,2,3 当前逆序对（只考虑i属于[1,2]，j属于[3,4]的逆序对）=0 逆序对个数的最大值：2*2-相同对数 = 3 2,3,1,2 答案 = 3-0 = 3 记录一下 所有连续2^k个数的当前逆序对个数，以及逆序对个数的最大值。
每次操作的时候，转变成平移操作 2^4 16
[x,y] 令 mid=(x+y)/2 对于所有i属于[x,mid] j属于[mid+1,y] 这样逆序对的个数
f[1]=[1,2]+[3,4]+[5,6]+...+[15,16]
f[2]=[1,4]+[5,8]+[9,12]+[13,16]
f[3]=[1,8]+[9,16]
f[4]=[1,16] g来表示最大的逆序对个数 (总共的对数-相同的对数) 对于每次对k进行操作
n^2*2^n
while (Q--)
{
cin>>k;
for (int i=1; i<=k; i++) f[i]=g[i]-f[i];
ans=0;
for (int i=1; i<=n; i++) ans+=f[i];
cout<<ans<<endl;
}
[1,4] [5,8] [5,8] [1,4] */
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
const int N=(<<)+;
long long st[N][],ST[N][];
int p[N],i,sum,o,a[N],b[N],n,T,PP,now,j,A,RR[N];
void gb(int l,int r)
{
if (l==r) return;
int mid=(l+r)/;
gb(l,mid); gb(mid+,r);
int i=l,j=mid+,o=l;
for (i=l; i<=r; i++) b[i]=a[i];
for (i=r; i>=mid; i--) {RR[i]=i; if (i!=r && b[i+]==b[i]) RR[i]=RR[i+];}
i=l; j=mid+;
while (i<=mid && j<=r)
{
if (b[i]<=b[j]) {a[o++]=b[i];if (b[i]==b[j]) ST[l][p[r-l+]]+=RR[j]-j+; i++;} else
{
a[o++]=b[j]; st[l][p[r-l+]]+=mid-i+; j++;
}
}
if (i<=mid) for (j=i; j<=mid; j++) a[o++]=b[j]; else
if (j<=r) for (i=j; i<=r; i++) a[o++]=b[i];
}
long long t[],TT[];
int main()
{
freopen("pair.in","r",stdin);
freopen("pair.out","w",stdout);
scanf("%d",&n);
sum=(<<n);
for (i=; i<=sum; i++) scanf("%d",&a[i]);
for (i=; i<=; i++) p[<<i]=i;
gb(,sum);
scanf("%d",&T);
for (i=; i<=n; i++)
for (j=; j<=(<<n); j+=(<<i))
{
t[i]+=st[j][i];
TT[i]+=ST[j][i];
}
long long ans=;
while (T--)
{
int Q;
scanf("%d",&Q);
for (i=; i<=Q; i++) t[i]=1ll*(<<i-)*(<<i-)*(<<n-i)-TT[i]-t[i];
for (i=; i<=n; i++) ans+=t[i];
printf("%I64d\n",ans); ans=;
}
return ;
}
100分 区间反转->区间平移