claris出题，orzzzzzz。前一天晚上说是贪心专场，喵喵喵？？？
之前clsris说难题扔多校了，据说07,13是女生赛撤下来的题，喵喵喵？？？
A.Ascending Rating
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6319
题意：给定一个序列 a[1..n]，对于每个长度为m的连续子区间，求出区间内ai的最大值以及从左往右扫描该区间时ai的最大值的变化次数。
分析：用pair型的deque去维护a的单调队列，队列中元素的个数就是最大值的变化次数。考虑倒着r从n到m去处理。
#include<iostream>
#include<cstring>
#include<queue>
#define maxn 10000005
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int a[maxn];
deque<pii> dq;
int n,m,k,p,q,r,mod;
int main(){
ios::sync_with_stdio(false);
cin.tie();cout.tie();
int t;
cin >> t;
while (t--){
cin >> n >> m >> k >> p >> q >> r >> mod;
for (int i=;i<=k;i++) cin >> a[i];
for (int i=k+;i<=n;i++) a[i]=(1ll*p*a[i-]+1ll*q*i+r)%mod;
dq.clear();
ll ansa=,ansb=;
for (int i=n-m+,j=n;i>=;i--){
while (j>=i){
while (!dq.empty() && dq.back().first<=a[j]) dq.pop_back();
dq.push_back({a[j],j});
j--;
}
while (dq.front().second>=i+m) dq.pop_front();
ansa+=dq.front().first^i;
ansb+=dq.size()^i;
}
cout << ansa << " " << ansb << endl;
}
return ;
}
hdoj6319
C.Dynamic Graph Matching
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6321
题意：给n（<=10）个点的无向图，有m（<=30000）次添加边或删除边的操作。问每次操作后，包含k=1,2,3...n/2条边的匹配数的方案数。
分析：将10个点用二进制位表示状态，总共有2^10种状态。每添加一条边，遍历（1<<n-1）到 0，寻找包含边（u，v）的状态，再累加上之前的方案数即可。同理，删除一条边，就减去之前的方案数。
最后，统一处理答案即可。需预处理出1024里所有二进制状态下包含1的个数，奇数个不符合直接coninue，将偶数个/2加入答案即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+;
const int N=;
int ans[];
int t,n,m;
ll dp[N];
int nn[N];
int solve(int x){
int res=;
while(x){
if(x&) res++;
x/=;
}
return res;
}
void init(){
for(int i=;i<=(<<)-;i++)
nn[i]=solve(i);
}
int main(){
char ch;int x,y;scanf("%d",&t);
init();
while(t--){
scanf("%d%d",&n,&m);
memset(dp,,sizeof(dp));
dp[]=;
for(int i=;i<=m;i++){
getchar();
scanf("%c %d %d",&ch,&x,&y);
if(ch=='+'){
for(int p=(<<n)-;p>=;p--){
if((p&(<<(x-)))==) continue;
if((p&(<<(y-)))==) continue;
int v=p^(<<(x-));v^=(<<(y-));
if(v>p) continue;
(dp[p]+=dp[v])%=mod;
}
}
else{
for(int p=(<<n)-;p>=;p--){
if((p&(<<(x-)))==) continue;
if((p&(<<(y-)))==) continue;
int v=p^(<<(x-));v^=(<<(y-));
if(v>p) continue;
dp[p]-=dp[v];
dp[p]=(dp[p]%mod+mod)%mod;
}
}
memset(ans,,sizeof(ans));
for(int p=(<<n)-;p>=;p--){
if(nn[p]%) continue;
(ans[nn[p]/]+=dp[p])%=mod;
}
for(int i=;i<=n/;i++){
if(i==) printf("%d",ans[]);
else printf(" %d",ans[i]);
}
printf("\n");
}
}
return ;
}
hdoj6321
D.Euler Function
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6322
题意：给定k，求第k小的数n，使得φ（n）是合数。
分析：欧拉函数：小于n的正整数中与n互质的数的数目（φ(1)=1）。打表。
#include<bits/stdc++.h>
using namespace std;
int main(){
int t,k;scanf("%d",&t);
while(t--){
scanf("%d",&k);
if(k==) printf("5\n");
else printf("%d\n",k+);
}
return ;
}
hdoj6322
F.Grab The Tree
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6324
题意：一棵结点数为n的树，每个点有权值。先手取若干不相邻的点，后手取剩下所有点。得分为所取结点权值的异或和，问最优策略下的结果。
分析：所有结点权值的异或和sum。
sum==0时，两人一定平均。其余情况，只要先手拿走sum二进制下最高位的那个1，那么一定可以取胜。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t,n; ll x,y;scanf("%d",&t);
while(t--){
ll cmp=;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%lld",&x),cmp^=x;
for(int i=;i<n;i++) scanf("%lld%lld",&x,&y);
if(cmp) printf("Q\n");
else printf("D\n");
}
return ;
}
hdoj6324
L.Visual Cube
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6330
题意：打印长a，宽b，高c的立方体。
分析：rt。
（写过最丑最乱的代码，就不粘了）