1.Senior's Array(hdu 5280)
题目大意：给出大小为N的数组和P,求将数组中的某个元素替换为P后的最大连续子段和。N<=1000
题解：
1.送分题,比赛的时候只想到枚举替换的元素然后贪心找最大连续子段和.时间复杂度O(N2)
2.实际上有更好的做法。类似线段树的合并,枚举替换元素的时候 可以把左右两边的答案合并.F[i]表示以i结尾,G[i]表示以i开头的最优解.合并的时候只要考虑把中间的P用起来,即
A[x]+max(0,F[x-1])+max(0,G[x+1]) . 时间复杂度O(N).
2.Senior's Gun(hdu 5281)
题目大意：给出两个大小分别为N,M的数组A,B,将这两个数组的元素配对起来,配对的得分为A[i]-B[j](只有A[i]>B[j]才可以把A[i],B[j]配对).要求得分和最大。
题解：
1.比赛的时候想到贪心地把A中大的和B中小的配对。 但是不会证明,感觉不大靠谱。然后就只A了T1 滚粗了。
2.官方题解很简洁：二分出最大可能的配对数,然后枚举配对数,取最大的答案。 这么简洁的题解像我这么弱的可能会一下反应不过来,所以来解释一下： 假设有2N个数能两两配对,那么配对的得分总和是一定的,即A的总和减去B的总和。 所以枚举了所有的配对数,也就枚举了所有的配对情况。 再提一下二分的时候怎么判断可行性：从小到大排序,然后小的和小的对,大的和大的对。 如果这样不行,那么一定不存在可行方案。 脑残的我又想来证明一下了（果然我不适合OI...OIer不是只要记住结论就好了么。。）：假设存在某种方案不是这样配对的,如果A,B数组已经从小到大排序，如果A[i]和B[j]配对就在他们之间连一条线。那么至少有两条线是交叉的.显然把交叉的线 弄成不交叉 即交换配对对象 也是满足条件的。 那么重复这样的操作 最终得到我们一开始的配对方式。
3.看了下别人的代码,发现1中的方法也是可行的。如果n<m 把B中最小的n个拿出来就好。 如果n>m把A中最大的m个拿出来就好。 所以只考虑n=m的情况。
考虑A中的两个元素P,Q,P<=Q. B中的两个元素S,T，S<=T.
如果Q<S，那么不能匹配任意一个.
如果P>=T，那么可以随便怎么匹配,得分为P+Q-S-T。 可以认为是PT,QS匹配。
除去上面的两种情况,也就是Q>=S,P<T的时候。这时候一定是QS匹配最优。我们可以从赚差值的角度理解。假设如果A[i]-A[j]<0也可以匹配,但实际得分却是0,这样我们就赚了
这个负的值。所以要想尽可能多赚这个负的值,要让A中小的P和B中大的T匹配。
。。憋出个证明蛋疼死了。而且感觉还是不大完美。 其实还是感觉官方题解好理解,但大多数人貌似都是3中的方法。
3.Senior's String(hdu 5282)
题目大意：给出2个字符串AB,求它们的LCS,假设长度是len,再求A中长度为len的子序列中有多少个是B的子序列。(一开始以为是LCS的个数,仔细想想其实不是。。)
题解：
先搞出求LCS时的dp数组。然后再做一次动态规划。F[i][j]表示A[1..i]的长度为dp[i][j]的子序列中有多少个是B[1...j]的子序列。
1.考虑不选A[i],那么必须有dp[i-1][j]==dp[i][j]. F[i][j]+=F[i-1][j].
2.考虑选 A[i],设p是满足p<=j && B[p]=A[i]的最大的p. 那么必须有dp[i-1][p-1]+1=dp[i][j] . F[i][j]+=F[i-1][p-1].
感觉这个dp略吊啊。
4.Senior's Fish(hdu 5283)
题目大意：
给出坐标系上的一个矩形,和一些点(编号1-N),要求支持以下操作：
1.把编号属于区间[L,R]的点横坐标+x(x>0).
2.把编号属于区间[L,R]的点纵坐标+x(x>0).
3.查询在矩形中点的个数。
题解：
1.这题要充分利用点的坐标是单调增的这个性质。 也就是说 一个点出了矩形 就不可能再进来了。 然后可以把询问拆成4个,有多少个点在某个点左下方的询问。
2.对xy坐标分别建4棵线段树,然后如果某个坐标超过了上界,就把它从线段树里删去。 这里有个技巧,就是可能一次操作之后有多个点超过了上界,但是这些点又不是连续的，我们可以一个一个删,因为每个点只会被删去一次,复杂度有保证. 只要每次找坐标值最大的点,如果越界了就删去,并把他的值改为负无穷。 具体实现起来好像有点麻烦,要好多线段树...我就没有写..懒。
5.wyh and pupil(hdu 5285)
题目大意：给出无向图的一些边,要求把点分为2个非空集合,集合内不能有边,且第一个集合点最多。
题解：
1.首先判断一下是不是二分图,如果不是无解。
2.可以发现连通块之间是独立的,只要每个连通块里选尽量多的点放到第一个集合就好。所以对每个连通块二分图染色,选择点多的那种颜色。
3.另外考虑特殊情况,只有一个点和没有边的情况。 比赛的时候没考虑 FST了。
6.wyh and sequence(hdu 5286)
题目大意：Q次询问区间[Li,Ri]中,把所有数去重之后,设第i个数pi出现了ki次, 求sigma(pi^ki).
题解：
1.这题写了4K左右的代码...BC难得有代码量这么大的题。感觉我就算会做也不可能在1个小时之内写出来A掉。跪nodgd分块大神！！
2.太难表述。。直接copy官方题解：
3.另外这题卡常数。。极限数据我的程序过不了,但是OJ上还是AC了。由于要离散化,我一开始写的时候每次都从map里取出那个元素...结果复杂度多了个log,死都查不出来。。
贴个代码：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cmath> 5 #include <vector> 6 #include <map> 7 #include <set> 8 #include <cstdlib> 9 #include <ctime> 10 #include <algorithm> 11 using namespace std; 12 13 typedef long long ll; 14 typedef pair<int,int> pii; 15 const int N=50010,Mod=1e9+7; 16 17 int n,Q,unit,tot; 18 int A[N],v[N],cnt[N],cur[N],ans[250][250],rk[N]; 19 int S[N][250],L[N],R[N],id[N],lb[250],rb[250]; 20 vector<int> g[N]; 21 map<int,int> mp; 22 23 inline int Add(int x,int y){return (x+y)%Mod;} 24 inline int Mul(int x,int y){return 1ll*x*y%Mod;} 25 26 void Init() 27 { 28 mp.erase(mp.begin(),mp.end()); tot=0; 29 for (int i=1;i<=n;i++) 30 { 31 if (!mp.count(A[i])) 32 { 33 mp[A[i]]=1; 34 v[++tot]=A[i]; 35 } 36 } 37 sort(v+1,v+tot+1); 38 for (int i=1;i<=tot;i++) mp[v[i]]=i; 39 for (int i=1;i<=n;i++) rk[i]=mp[A[i]]; 40 41 for (int i=1;i<=tot;i++) g[i].clear(),g[i].push_back(0),cur[i]=1; 42 for (int i=1;i<=n;i++) 43 { 44 cur[rk[i]]=Mul(cur[rk[i]],A[i]); 45 g[rk[i]].push_back(cur[rk[i]]); 46 } 47 48 unit=sqrt(n)+1; 49 L[1]=1,id[1]=1; 50 for (int i=2;i<=n;i++) 51 { 52 id[i]=(i-1)/unit+1; 53 L[i]=(id[i]==id[i-1])? L[i-1]:i; 54 } 55 R[n]=n; 56 for (int i=n-1;i>=1;i--) R[i]=(id[i]==id[i+1])? R[i+1]:i; 57 58 for (int i=1;i<=id[n];i++) lb[i]=(i-1)*unit+1,rb[i]=min(i*unit,n); 59 60 for (int i=1;i<=tot;i++) cnt[i]=0; 61 for (int i=1;i<=n;i++) 62 { 63 cnt[rk[i]]++; 64 if (i%unit==0 || i==n) 65 { 66 for (int j=1;j<=tot;j++) 67 S[j][id[i]]=cnt[j]; 68 } 69 } 70 71 72 for (int i=1;i<=id[n];i++) 73 { 74 for (int j=1;j<=tot;j++) cnt[j]=0; 75 for (int j=i;j<=id[n];j++) 76 { 77 ans[i][j]=(i==j)? 0:ans[i][j-1]; 78 for (int k=lb[j];k<=rb[j];k++) 79 { 80 int x=rk[k]; cnt[x]++; 81 ans[i][j]=Add(ans[i][j],-g[x][cnt[x]-1]); 82 ans[i][j]=Add(ans[i][j],g[x][cnt[x]]); 83 ans[i][j]=Add(ans[i][j],Mod); 84 } 85 } 86 } 87 memset(cnt,0,sizeof(cnt)); 88 } 89 90 int Query(int l,int r) 91 { 92 int Ans=0; 93 if (id[r]-id[l]<=1) 94 { 95 for (int i=l;i<=r;i++) 96 { 97 int x=rk[i]; 98 Ans=Add(Ans,-g[x][cnt[x]]); 99 Ans=Add(Ans,g[x][++cnt[x]]); 100 Ans=Add(Ans,Mod); 101 } 102 for (int i=l;i<=r;i++) cnt[rk[i]]=0; 103 } 104 else 105 { 106 Ans=ans[id[l]+1][id[r]-1]; 107 for (int i=l;i<=R[l];i++) 108 { 109 int x=rk[i]; 110 Ans=Add(Ans,-g[x][cnt[x]+S[x][id[r]-1]-S[x][id[l]]]); 111 Ans=Add(Ans,g[x][++cnt[x]+S[x][id[r]-1]-S[x][id[l]]]); 112 Ans=Add(Ans,Mod); 113 } 114 for (int i=L[r];i<=r;i++) 115 { 116 int x=rk[i]; 117 Ans=Add(Ans,-g[x][cnt[x]+S[x][id[r]-1]-S[x][id[l]]]); 118 Ans=Add(Ans,g[x][++cnt[x]+S[x][id[r]-1]-S[x][id[l]]]); 119 Ans=Add(Ans,Mod); 120 121 } 122 for (int i=l;i<=R[l];i++) cnt[rk[i]]=0; 123 for (int i=L[r];i<=r;i++) cnt[rk[i]]=0; 124 } 125 return Ans; 126 } 127 128 void Read(int &x) 129 { 130 x=0; char ch=getchar(); 131 while (ch<'0' || ch>'9') ch=getchar(); 132 while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); 133 } 134 135 int main() 136 { 137 int T,lastans,x,y,l,r;scanf("%d",&T); 138 while (T--) 139 { 140 scanf("%d%d",&n,&Q); 141 for (int i=1;i<=n;i++) Read(A[i]); 142 Init(); lastans=0; 143 for (int i=1;i<=Q;i++) 144 { 145 Read(x),Read(y); 146 x^=lastans,x%=n,x++; 147 y^=lastans,y%=n,y++; 148 l=min(x,y),r=max(x,y); 149 lastans=Query(l,r); 150 printf("%d ",lastans); 151 } 152 } 153 154 return 0; 155 }