-
1 .七夕祭
书上的推导过程口头描述了一遍->传送门
好像啰嗦了一点哈哈哈哈哈哈
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N=1e5+10;
ll a[N],b[N],c[N],s[N];
ll calc(ll c[],ll M)
{
ll ans=0;
for(int i=1;i<=M;i++)
{
c[i]-=c[0]/M;
s[i]=s[i-1]+c[i];
}
sort(s+1,s+M+1);
for(int i=1;i<=M;i++)ans+=abs(s[i]-s[M+1>>1]);
return ans;
}
int main()
{
ll n,m,t;
scanf("%lld%lld%lld",&n,&m,&t);
for(int i=1;i<=t;i++)
{
ll x,y;
scanf("%lld%lld",&x,&y);
a[x]++,b[y]++;
}
for(int i=1;i<=t;i++)a[0]+=a[i];
for(int i=1;i<=t;i++)b[0]+=b[i];
if(a[0]%n==0&&b[0]%m==0)
cout<<"both "<<calc(a,n)+calc(b,m)<<endl;
else if(a[0]%n==0)
cout<<"row "<<calc(a,n)<<endl;
else if(b[0]%m==0)
cout<<"column "<<calc(b,m)<<endl;
else
cout<<"impossible"<<endl;
return 0;
}
-
2 .Running Median
动态维护中位数问题：依次读入一个整数序列，每当已经读入的整数个数为奇数时，数除以读入的整数构成的序列的中位数。
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t,n,m;
cin>>t;
while(t--)
{
priority_queue<int>q;//q为大根堆
priority_queue<int,vector<int>,greater<int> > p;//p为小根堆
cin>>n>>m;
cout<<n<<" "<<(m+1)/2<<endl;
int cnt=0;
for(int i=1;i<=m;i++)
{
cin>>n;
//先插小根堆，小根堆堆顶为中位数
p.push(n);
//如果大根堆的堆顶元素比小根堆堆顶要大,且大根堆非空,交换即可
if(q.size()&&q.top()>p.top())
{
int a=q.top();
int b=p.top();
p.pop();
q.pop();
q.push(b);
p.push(a);
}
//维护小根堆数量始终比大根堆多一个
if(p.size()>q.size()+1)
{
q.push(p.top());
p.pop();
}
if(i&1)
{
cnt++;
printf("%d",p.top());
if(cnt%10==0)
printf("\n");
else
printf(" ");
}
}
//不满足十个数，要换行重新读入
if(cnt%10)cout<<endl;
}
return 0;
}
-
3 . 第k大数（分治）
—>传送门
-
4. 逆序对（归并排序逆序对问题）
—>传送门
-
5. Ultra-QuickSort(超快速排序)（归并排序逆序对问题）
如果只允许进行比较和交换相邻两个数的操作，求至少需要多少次交换才能把a从小到大排序
直接使用归并排序求出a的逆序对数就是本题的答案
#include <iostream>
#define ll long long
using namespace std;
const int N=1e6+10;
ll n,res;
ll a[N],temp[N];
ll merge_sort(int l,int r)
{
if(l==r) return 0;
int mid=(l+r)>>1;
ll res=merge_sort(l,mid)+merge_sort(mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j]) temp[k++]=a[i++];
else
{
temp[k++]=a[j++];
res+=mid-i+1;
}
}
while(i<=mid)temp[k++]=a[i++];
while(j<=r)temp[k++]=a[j++];
for(int i=l,j=0;i<=r;i++,j++)
a[i]=temp[j];
return res;
}
int main()
{
while(cin>>n&&n)
{
res=0;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<merge_sort(0,n-1)<<endl;
}
return 0;
}
-
6 . 奇数码问题（归并排序逆序对问题）
现给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一种局面可以变化到另外一种局面。
本题特别要注意，0是代表空格，而不是0，不能算入逆序对
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],b[N],temp[N];
int n;
int merge_sort(int l,int r,int ans[])
{
if(l==r) return 0;
int mid=(l+r)>>1;
int res=merge_sort(l,mid,ans)+merge_sort(mid+1,r,ans);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r)
{
if(ans[i]<=ans[j]) temp[k++]=ans[i++];
else
{
temp[k++]=ans[j++];
res+=mid-i+1;
}
}
while(i<=mid)temp[k++]=ans[i++];
while(j<=r)temp[k++]=ans[j++];
for(int i=l,j=0;i<=r;i++,j++)
ans[i]=temp[j];
return res;
}
int main()
{
while(cin>>n&&n)
{
int ans1,ans2,k=0,j=0;
for(int i=0;i<n*n;i++)
{
int x;
scanf("%d",&x);
if(x!=0)a[k++]=x;
}
ans1=merge_sort(0,n*n-1,a);
for(int i=0;i<n*n;i++)
{
int y;
scanf("%d",&y);
if(y!=0)b[j++]=y;
}
ans2=merge_sort(0,n*n-1,b);
if((ans1&1)==(ans2&1))
printf("TAK\n");
else
printf("NIE\n");
}
return 0;
}
