7.2训练日记

中间是学校的小学期,乌烟瘴气地搞了十几天,自己也有点懈怠了,好好反思,继续训练。 1.H. Gambling 最后抽象成一个问题:在x-y坐标系选择一个适当的值y.使得这条直线上的点的贡献尽量大.贡献计算方法为:选择一个区间 [ L , R ] [L,R] [L,R],令tot为该区间上点的数目.贡献= t o t − ( R − L + 1 − t o t ) = 2 ∗ t o t − l e n tot-(R-L+1-tot)=2*tot-len tot−(R−L+1−tot)=2∗tot−len 尝试用贪心解决该问题:记录一个值 n o w now now为上一个区间/当前区间的贡献值,只要贡献值大于1,总是能通过亏损中间区间长度的方法把当前考虑的i加入到之前计算的贡献中.否则我们可以考虑另开一个新区间.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
map ID,ID1;int ID_num=0;
int id(int x){
	if(!ID.count(x)) ID[x] = ID_num++;
	return ID[x];
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	while(T--){
		int n;cin>>n;
		ID_num = 0;ID.clear();ID1.clear();
		vector a(n+1);
		for(int i=1,x;i>x;a[id(x)].push_back(i);
			ID1[id(x)] = x;
		}
		int ans = 0,y,l,r;
		for(int i=0;i0){
						res= (res-(a[i][j]-R-1)+1);
						R = a[i][j];
						if(res>ans){
							ans = res;
							y = ID1[i];
							l = L,r = R; 
						}
					}
					else {
						res = 1;L = R = a[i][j];
						if(res>ans) {
							ans = res;y = ID1[i];
							l=L,r=R;
						}
					}
				}
			}
		}
		cout