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去处理。
1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 #define maxn 10000005 5 using namespace std; 6 typedef long long ll; 7 typedef pair<int,int> pii; 8 int a[maxn]; 9 deque<pii> dq; 10 int n,m,k,p,q,r,mod; 11 int main(){ 12 ios::sync_with_stdio(false); 13 cin.tie(0);cout.tie(0); 14 int t; 15 cin >> t; 16 while (t--){ 17 cin >> n >> m >> k >> p >> q >> r >> mod; 18 for (int i=1;i<=k;i++) cin >> a[i]; 19 for (int i=k+1;i<=n;i++) a[i]=(1ll*p*a[i-1]+1ll*q*i+r)%mod; 20 dq.clear(); 21 ll ansa=0,ansb=0; 22 for (int i=n-m+1,j=n;i>=1;i--){ 23 while (j>=i){ 24 while (!dq.empty() && dq.back().first<=a[j]) dq.pop_back(); 25 dq.push_back({a[j],j}); 26 j--; 27 } 28 while (dq.front().second>=i+m) dq.pop_front(); 29 ansa+=dq.front().first^i; 30 ansb+=dq.size()^i; 31 } 32 cout << ansa << " " << ansb << endl; 33 } 34 return 0; 35 }
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加入答案即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod=1e9+7; 5 const int N=3000; 6 int ans[11]; 7 int t,n,m; 8 ll dp[N]; 9 int nn[N]; 10 int solve(int x){ 11 int res=0; 12 while(x){ 13 if(x&1) res++; 14 x/=2; 15 } 16 return res; 17 } 18 void init(){ 19 for(int i=1;i<=(1<<11)-1;i++) 20 nn[i]=solve(i); 21 } 22 int main(){ 23 char ch;int x,y;scanf("%d",&t); 24 init(); 25 while(t--){ 26 scanf("%d%d",&n,&m); 27 memset(dp,0,sizeof(dp)); 28 dp[0]=1; 29 for(int i=1;i<=m;i++){ 30 getchar(); 31 scanf("%c %d %d",&ch,&x,&y); 32 if(ch=='+'){ 33 for(int p=(1<<n)-1;p>=0;p--){ 34 if((p&(1<<(x-1)))==0) continue; 35 if((p&(1<<(y-1)))==0) continue; 36 int v=p^(1<<(x-1));v^=(1<<(y-1)); 37 if(v>p) continue; 38 (dp[p]+=dp[v])%=mod; 39 } 40 } 41 else{ 42 for(int p=(1<<n)-1;p>=0;p--){ 43 if((p&(1<<(x-1)))==0) continue; 44 if((p&(1<<(y-1)))==0) continue; 45 int v=p^(1<<(x-1));v^=(1<<(y-1)); 46 if(v>p) continue; 47 dp[p]-=dp[v]; 48 dp[p]=(dp[p]%mod+mod)%mod; 49 } 50 } 51 memset(ans,0,sizeof(ans)); 52 for(int p=(1<<n)-1;p>=0;p--){ 53 if(nn[p]%2) continue; 54 (ans[nn[p]/2]+=dp[p])%=mod; 55 } 56 for(int i=1;i<=n/2;i++){ 57 if(i==1) printf("%d",ans[1]); 58 else printf(" %d",ans[i]); 59 } 60 printf(" "); 61 } 62 } 63 return 0; 64 }
D.Euler Function
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6322
题意：给定k，求第k小的数n，使得φ（n）是合数。
分析：欧拉函数：小于n的正整数中与n互质的数的数目（φ(1)=1）。打表。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main(){ 4 int t,k;scanf("%d",&t); 5 while(t--){ 6 scanf("%d",&k); 7 if(k==1) printf("5 "); 8 else printf("%d ",k+5); 9 } 10 return 0; 11 }
F.Grab The Tree
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6324
题意：一棵结点数为n的树，每个点有权值。先手取若干不相邻的点，后手取剩下所有点。得分为所取结点权值的异或和，问最优策略下的结果。
分析：所有结点权值的异或和sum。
sum==0时，两人一定平均。其余情况，只要先手拿走sum二进制下最高位的那个1，那么一定可以取胜。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int main(){ 5 int t,n; ll x,y;scanf("%d",&t); 6 while(t--){ 7 ll cmp=0; 8 scanf("%d",&n); 9 for(int i=1;i<=n;i++) scanf("%lld",&x),cmp^=x; 10 for(int i=1;i<n;i++) scanf("%lld%lld",&x,&y); 11 if(cmp) printf("Q "); 12 else printf("D "); 13 } 14 return 0; 15 }
L.Visual Cube
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6330
题意：打印长a，宽b，高c的立方体。
分析：rt。
（写过最丑最乱的代码，就不粘了）