A - ^&^
题意：
t组样例，每组样例给你一个A和B，你需要求一个最小的C使得(A xor C) & (B xor C)的值最小。
思路：
em....乘法分配律？提取出A和B先进行与（&）操作，然后在异或C，因为异或相同为0，不同为1，你想要最小的肯定C要等于A&B，这里注意，如果求出的C=0，要输出1。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
long long ans;
long long a,b;
cin>>a>>b;
ans=a&b;
if(ans==0)
cout<<1<<endl;
else
cout<<ans<<endl;
}
}F - Shuffle Card
题意：
给你两个数n和m，你现在有n个从1到n的卡片，接下来你有m个操作，每个操作输入一 个卡片数字，接下来你要把这个数字提到第一位，其他的依次往后退，输出m个操作后卡片的顺序。
思路：
a[i]存一下卡片，用vis[i] 去标记a[i] 数组的每个数，m个操作可以发现，你从后往前存入b数组不就是这个卡片的顺序了么，因为是从后往前执行的操作，这其中已经放在开头的将其vis[i]标记为0代表已经存过了，当你存完这m个操作提前的卡片数字后（存完的vis[i]都标记为0了），剩下的（即vis[i]为1）依次存放即可。注意：它输出时每个数字后都要有一个空格，并且不能换行，这两个坑都踩了QAQ。
代码：
#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],op[100005],vis[100005];
int main()
{
ios::sync_with_stdio(false);
memset(vis,0,sizeof(vis));
long long ans;
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>a[i];
vis[a[i]]=1;
}
for(int i=1; i<=m; i++)
cin>>op[i];
int k=1;
for(int i=m; i>=1; i--)
{
if(vis[op[i]])
{
b[k++]=op[i];
vis[op[i]]=0;
}
}
for(int i=1; i<=n; i++)
{
if(vis[a[i]])
{
b[k++]=a[i];
vis[a[i]]=0;
}
}
for(int i=1; i<=n; i++)
{
cout<<b[i]<<" ";
}
}G - Windows Of CCPC
题意：
输入一个n，找出对应的图案。
n=1
CC
PC
n=2
CCCC
PCPC
PPCC
CPPC
n=3
CCCCCCCC
PCPCPCPC
PPCCPPCC
CPPCCPPC
PPPPCCCC
CPCPPCPC
CCPPPPCC
PCCPCPPC思路：
模拟，就是将图案复制四份，而在左下角的全部取反（即P为C，C为P）。
因为n=1 是2阶矩阵，n=2 是4阶矩阵，n=3 是8阶矩阵
所以每个矩阵大小为2的n次方
假设我们将第一阶窗口化为4个区，可以发现1、2、4区的符号是一样的，第三个区与其他区符号是‘相反’的（C就转为P，P就转为C）。
在第二阶及以上的情况下，我们可以知道它是以上一阶窗口为基础，将上一阶窗口认为是1区，各区之间的关系与一阶相似。注意，第三区的所有符号都要与其他区的符号‘相反’。
三阶及以上阶窗口与上面推导过程相似。
由于题目的数据比较小，所以我们就可以直接用数组预处理，到时候直接输出就好了。需要注意的是，我们可以发现每一阶窗口的大小是2的k次方（k为阶数）。所以第2区的横坐标范围是从2的（k次方-1）+1 ~ 2的k次方，纵坐标范围是从1 ~ 2的k次方-1（博主把初始化起点定为1）。其他区与此类似。
代码：
#include<iostream>
#include<cmath>
using namespace std;
const int MAX = 1024+5;
char mp[MAX][MAX];
int main(void)
{
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
mp[1][1] = 'C'; //初始化最原始的左上角
mp[1][2] = 'C';
mp[2][1] = 'P';
mp[2][2] = 'C';
int k = 1;//阶数
for(int i=1; i<=n; i++)
{
int x1 = pow(2,k);
int x2 = pow(2,k-1);
for(int i=1; i<=x2; i++) //右上角 （以左上角为参照，即纵坐标-x2位置赋值给当前位置）
{
for(int j=x2 + 1; j<=x1; j++)
{
mp[i][j] = mp[i][j-x2];
}
}
for(int i=x2 + 1; i<=x1; i++) //右下角 （以右上角为参照，即横坐标-x2位置赋值给当前位置）
{
for(int j=x2 + 1; j<=x1; j++)
{
mp[i][j] = mp[i-x2][j];
}
}
for(int i=x2 + 1; i<=x1; i++) //左下角 （以左上角为参照，即纵坐标-x2位置翻转赋值给当前位置）
{
for(int j=1; j<=x2; j++)
{
if(mp[i-x2][j] == 'C')
{
mp[i][j] = 'P';
}
if(mp[i-x2][j] == 'P')
{
mp[i][j] = 'C';
}
}
}
k++;
}
int x = pow(2,n);
for(int i=1; i<=x; i++)
{
for(int j=1; j<=x; j++)
{
cout << mp[i][j];
}
cout << endl;
}
}
return 0;
}
H - Fishing Master
题意：
有n条鱼，每条鱼要煮相应的时间才能吃，捕一条鱼的时间是相同的，在捕鱼的时间内不能做其他事，可以捕多条鱼，求把所有的鱼都煮熟需要多少时间。
思路：
首先我们第一次捕鱼和所有的炖鱼时间都要计入答案，再煮鱼的时候我们可以去选择钓鱼，但是我们最多钓a[i]/k条鱼，此时我们有一个选择就是，要不要多花k-（a[i]%k）的时间去多钓一条鱼，仔细思考一下，就是如果我们随后不缺鱼可炖，肯定不需要多花这个时间，但是万一我们后边缺鱼了，那么我们必须多花这个时间，所以，我们把这个时间入一个优先队列，如果后边需要煮鱼但是手里鱼数量不够了，此时必须去前边多花一点时间换一条鱼，取队首就好了。
题解：
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN = 1e5+5;
ll a[MAXN];
priority_queue<ll,vector<ll>,greater<ll> >q;
bool cmp(ll a,ll b)
{
return a>b;
}
int main()
{
ll t,n,k;
scanf("%lld",&t);
while(t--)
{
while(!q.empty())
q.pop();
scanf("%lld%lld",&n,&k);
for(ll i=1; i<=n; i++)
scanf("%lld",&a[i]);
sort(a+1,a+n+1,cmp);
ll ans=k,num=1;
for(ll i=1; i<=n; i++)
{
ans+=a[i];
if(num>=i)
{
num+=a[i]/k;
q.push(k-(a[i]%k));
continue;
}
if(q.empty())
ans+=k;
else
{
ans+=q.top();
q.pop();
}
num+=a[i]/k;
q.push(k-(a[i]%k));
}
printf("%lld\n",ans);
}
return 0;
}
D - path
题意：
无向图，n个点，m条有权边，求第k短的路径多长。
思路：
bfs，要注意的是，如果扩展每个可以到达的点，一定会超时+爆栈，其实这样做是没有必要的，每一次只用扩展同一层的点以及所有连边中最小的所指向的那个点。
先把全部的边入队列，然后再往外bfs。每次取队首，然后接上一个点，再塞回去，把查询离线，然后记录前max(k)取队首，就可以O（1）访问了。
直接优先队列模拟的话，会被菊花图卡时间和空间，所以要加一个优化，优先队列改用set，保证每次set里最多只有max(k)个元素
题解：
代码：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const ll MAXN = 5e4+5;
const ll MOD = 1e9+7;
struct node
{
ll x,y;
ll val;
bool operator <(const node &r)const
{
return val<r.val;
}
} a,b;
multiset<node>s;
struct nod
{
ll to,val;
} p;
vector<nod>v[MAXN],g[MAXN];
ll ans[MAXN],c[MAXN];
bool cmp(nod a,nod b)
{
return a.val<b.val;
}
int main()
{
ll t,n,m,Q,u,V,w;
scanf("%lld",&t);
while(t--)
{
ll maxx=0;
scanf("%lld%lld%lld",&n,&m,&Q);
s.clear();
for(ll i=1; i<=n; i++)
v[i].clear();
while(m--)
{
scanf("%lld%lld%lld",&u,&V,&w);
p.to=V,p.val=w;
v[u].push_back(p);
a.x=u,a.y=V;
a.val=w;
s.insert(a);
}
for(ll i=1; i<=n; i++)
sort(v[i].begin(),v[i].end(),cmp);
for(ll i=1; i<=Q; i++)
{
scanf("%lld",&c[i]);
maxx=max(maxx,c[i]);
}
ll pos=0;
multiset<node>::iterator it;
while(!s.empty())
{
a=*s.begin();
s.erase(s.begin());
ans[++pos]=a.val;
if(pos==maxx)break;
int len=v[a.y].size();
for(ll i=0; i<=len-1; i++)
{
b=a;
b.y=v[a.y][i].to;
b.val+=v[a.y][i].val;
if(s.size()>maxx-pos)
{
it=s.end();
it--;
if((*it).val>b.val)
{
s.erase(it);
s.insert(b);
}
else break;
}
else
{
s.insert(b);
}
}
}
for(ll i=1; i<=Q; i++)
{
printf("%lld\n",ans[c[i]]);
}
}
return 0;
}
