B - Balanced Sequence
预处理出每个串未匹配的)及(的个数，看这个范围大致可以猜出是贪心。然而博主单纯的按照(从大到小排序。。看了题解才发现还能这样。。
这题主要的trick是排序方式，记好了!
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node
{int L,R;int idx;node(int L,int R,int idx):L(L),R(R),idx(idx){}node(){}
}t[maxn];
char s[maxn];
long long sum;
void solve(int idx)
{int l=0,r=0;int num=0;int len=strlen(s);for(int i=0;i<len;i++){if(s[i]=='('){num++;}else{if(num==0){r++;}else{num--;sum+=2;}}}l=num;t[idx].L=l,t[idx].R=r,t[idx].idx=idx;
}
bool cmpl(const node &a,const node &b)
{if(a.L<a.R&&b.L>b.R)return false;else if(a.L<a.R&&b.L<b.R)return a.L>b.L;else if(a.L>=a.R&&b.L<b.R)return 1;else return a.R<b.R;
}
long long dp[maxn];
long long suml[maxn];
int main()
{int T;scanf("%d",&T);while(T--){sum=0;int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s);solve(i);}sort(t+1,t+1+n,cmpl);for(int i=1;i<=n;i++){long long r=t[i].R;long long tmp=min(r,suml[i-1]-dp[i-1]);dp[i]=dp[i-1]+tmp;suml[i]=suml[i-1]+t[i].L;}sum+=2LL*dp[n];printf("%lld\n",sum);}return 0;
}D - Distinct Values
这题还是挺好做的，排个序之后从左到右依次处理每个区间，再开个数组看当前区间那些数被用了。实际上这个做法比较像莫队的转移。。
#include<bits/stdc++.h>
using namespace std;
const int maxm=1e5+5;
const int maxn=1e5+5;
typedef pair<int,int>pii;
pii facts[maxm];
int num[maxn];
int ans[maxn];bool cmp(pii a,pii b)
{if(a.first!=b.first)return a.first<b.first;return a.second>b.second;
}int main()
{int T;scanf("%d",&T);while(T--){memset(num,0,sizeof(num));memset(ans,-1,sizeof(ans));int n,m;scanf("%d %d",&n,&m);int l,r;for(int i=1;i<=m;i++){scanf("%d %d",&l,&r);facts[i]=make_pair(l,r);}sort(facts+1,facts+1+m,cmp);for(int i=1;i<=facts[1].first;i++)ans[i]=1;for(int i=facts[1].first;i<=facts[1].second;i++)ans[i]=i-facts[1].first+1,num[i-facts[1].first+1]=1;int lnode=facts[1].first,rnode=facts[1].second;for(int i=2;i<=m;i++){if(facts[i].second<=rnode)continue;if(facts[i].first>rnode){memset(num,0,sizeof(num));for(int j=rnode+1;j<=facts[i].first;j++)ans[j]=1;for(int j=facts[i].first;j<=facts[i].second;j++){ans[j]=j-facts[i].first+1;num[j-facts[i].first+1]=1;}lnode=facts[i].first,rnode=facts[i].second;}else{for(int j=lnode;j<facts[i].first;j++){num[ans[j]]=0;}int now=1;for(int j=rnode+1;j<=facts[i].second;j++){while(num[now])now++;ans[j]=now;num[now++]=1;}lnode=facts[i].first;rnode=facts[i].second;}}for(int i=1;i<=n;i++){if(i!=1)printf(" ");if(ans[i]==-1)ans[i]=1;printf("%d",ans[i]);}puts("");}return 0;
}G - Chiaki Sequence Revisited
这个题真的强!
首先观察出每个数(除了1)出现的次数为lowbit(x)的长度，比如16为10000，那么他就会出现5次。
然后怎么做呢，既然和它的lowbit有关，那么我们就用位运算的思想做这个题，设一个数为x，那么显然x>>i就为至少出现(i+1)次的数的个数，你如果每一层都这样计算的话，实际上算的就是小于等于x的数出现次数的和。
通过这种思想，我们也可以求出小于等于x的数的和。
所以我们可以二分算出第n项是哪个数，然后再用等差数列求和算出前n项的和。
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n;
bool check(long long num)
{long long res=0;for(int i=0;i<63;i++){res+=(num>>i);if(res>=n-1)return 1;}return res>=n-1;
}
long long inv(long long a,long long m)
{if(a==1)return 1;return inv(m%a,m)*(m-m/a)%m;
}int main()
{int T;scanf("%d",&T);long long inv2=inv(2,mod);while(T--){scanf("%lld",&n);if(n==1){puts("1");continue;}else if(n==2){puts("2");continue;}long long l=2,r=n;long long ans;while(l<=r){long long mid=l+r>>1;if(check(mid)){ans=mid;r=mid-1;}else l=mid+1;}long long res=1;long long tmp=ans-1;long long go=1;for(int i=0;i<63;i++){if((1LL<<i)>tmp)break;long long tmp2=(tmp>>i);go+=tmp2;////if(tmp2%2)tmp2=(tmp2+1)/2*tmp2%mod;//else tmp2=tmp2/2*(tmp2+1)%mod;tmp2=tmp2%mod*((tmp2+1)%mod)%mod*inv2%mod;res=(res+(1LL<<i)%mod*tmp2%mod)%mod;}n=n-go;res=(res+n*ans%mod)%mod;printf("%lld\n",res);}return 0;
}