昨天的B题，昨天做的时候没注意所有谷堆是全排列，看了Clarification才知道，可是不会做。
实际上只需要将自己的代码改动一步就可以了count = count*(c[i]-b[i]-i+2)%mod，也即c[i]-b[i]+1-(i-1)
看这个样例就知道了
4
2 1 1 1
2 2 5 5
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn = 1e5+5; const int mod = 998244353; int b[maxn]; int c[maxn]; int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i = 1; i<=n; i++) { scanf("%d",&b[i]); } for(int i = 1; i<=n; i++) { scanf("%d",&c[i]); } int flag = 0; if(c[1]!=b[1]) flag = 1; long long count = 1; for(int i = 2; i<=n; i++) { if((c[i]!=c[i-1]&&b[i]!=b[i-1])||c[i]<c[i-1]||b[i]>b[i-1]) { flag = 1; break; } if(b[i]==b[i-1]&&c[i]==c[i-1]) { count = count*(c[i]-b[i]-i+2)%mod; if(c[i]-b[i]-i+2==0) { flag = 1; break; } } } if(flag) printf("0 "); else printf("%I64d ",count); } return 0; }
题目链接：HDU 5583 Kingdom of Black and White
神题。模拟练习的时候思路和其他同学的一样，可就是一直T。
搁了几天，今天推了重写。先WA了几发。觉得不会爆int啊，才10^10，和2147483647还少很多呢。就这样的sb错误，int的范围是2×10^9.
预处理01.
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn = 1e5+5; typedef long long ll; char s[maxn]; ll pre[maxn]; ll f(ll x) { return x*x; } int main() { int t,kase = 0; cin>>t; while(t--) { memset(pre,0,sizeof(pre)); scanf("%s",s); int n = strlen(s); int ans = 1; ll sum = 0; for(int i = 0; i<n; i++) { pre[ans]++; if(s[i]!=s[i+1]) { sum += f(pre[ans]); ans++; } } ll cnt = 0; ll maxn = sum; for(int i = 1; i<ans; i++) { if(pre[i]==1) { cnt = pre[i-1]+pre[i]+pre[i+1]; cnt = f(cnt) - f(pre[i-1])-f(pre[i])-f(pre[i+1]); cnt += sum; maxn = max(maxn,cnt); } else { if(i<ans-1) { cnt = f(pre[i]-1)+f(pre[i+1]+1)-f(pre[i])-f(pre[i+1]); cnt += sum; maxn = max(maxn,cnt); } if(i>1) { cnt = f(pre[i]-1)+f(pre[i-1]+1)-f(pre[i])-f(pre[i-1]); cnt += sum; maxn = max(maxn,cnt); } } } printf("Case #%d: %I64d ",++kase,maxn); } return 0; }
学会了二叉树，谢谢一神。
二叉树的翻转。
晚上cf模拟练。
CodeForces 500B New Year Permutation
B题，刚开始做的时候想简单了，认为只需要把最大的并且可以和后面交换就交换，实际上，它为了达到一个最优的目的，过程中可以把最大的先和前面的某一元素交换，最后再换回来。
可以 并查集构造联通性。 判断两点是否联通可以floyd.
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 305; int cnt[maxn]; char ans[maxn][maxn]; int main() { int n; cin>>n; for(int i = 1; i<=n; i++) scanf("%d",&cnt[i]); for(int i = 1; i<=n; i++) { scanf("%s",ans[i]+1); } for(int k = 1; k<=n; k++) for(int i = 1; i<=n; i++) for(int j = 1; j<=n; j++) if(ans[i][k]=='1'&&ans[k][j]=='1') { ans[i][j] = ans[j][i] = '1'; } for(int i = 1; i<n; i++) for(int j = i+1; j<=n; j++) { if(cnt[i]>cnt[j]&&ans[i][j]=='1') { swap(cnt[i],cnt[j]); } } for(int i = 1; i<n; i++) printf("%d ",cnt[i]); printf("%d ",cnt[n]); return 0; }
CodeForces 500C New Year Book Reading
贪心。考虑局部最优解。
先看这组样例。 看书顺序 1 1 1 3 2 1 1
在取x=2本书时，不管前面的初始顺序是什么，此时的顺序一定是3 1 2，所以只要使初始顺序到3 1 2取得书的质量最小即可。
然后考虑局部的某个取书子序列a b,如果书的顺序是a b,那么产生的费用就是w[b].如果书的顺序是b a,那么产生的费用w[a]+w[b].
最后得出初始顺序即为每本书第一次出现的顺序。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn = 505; int w[maxn]; int sq[maxn*2]; int inin[maxn]; int vis[maxn]; int main() { int n,m; cin>>n>>m; for(int i = 1; i<=n; i++) scanf("%d",&w[i]); for(int i = 1; i<=m; i++) scanf("%d",&sq[i]); int ans = 1; int summ = 0; int sum = 0; for(int i = 1; i<=m; i++) { if(!vis[sq[i]]) { vis[sq[i]] = 1; inin[ans] = sq[i]; ans++; } } for(int i = 1; i<=m; i++) { sum = 0; for(int j = 1; j<ans; j++) { if(inin[j]==sq[i]) { summ += sum; for(int k = j; k>=2; k--) { inin[k] = inin[k-1]; } inin[1] = sq[i]; break; } else sum += w[inin[j]]; } } printf("%d ",summ); return 0; }