C题冲刺计划（0/50）
1C
//从贡献的角度看待这道题，首先我们构造三个数，最优解就是两相同一个不同，
//从而保证最优，由于01的对称性，我们只需要保证这一位上两个数的二进制
//不同，另一个数随机，且由于位次越高越生成的值越多
//所以我们贪心的构造2的k次方和2k次方-1保证有最多的不同的1
//这个k是最开始位
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ll l,r;
cin>>l>>r;
int k=0;
ll num=l^r;
for(int i=40;i>=0;i--){
if((num>>i)&1){
k=i;
break;
}
}
ll a=l|(((ll)1<<k)-1);//这样子既不会超过r，也不会小于l
ll b,c;
b=a+1;
if(a!=l){
c=l;
}else{
c=r;
}
cout<<a<<" "<<b<<" "<<c<<"\n";
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}
2C
//使得相邻两个数的和不是质数，首先我们知道i+1和i是互质
//相加起来发现5 4是不是质数，但是绝大多数是质数，所以我们可以
//知道奇数加奇数或者偶数加偶数结果都是偶数，那么可以通过5 4作为
//桥梁
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin>>n;
if(n<=4) cout<<-1<<"\n";
else if(n==5) cout<<"1 3 5 4 2\n";
else{
for(int i=1;i<=n;i+=2){
if(i==5) continue;
else cout<<i<<" ";
}
cout<<5<<" ";
cout<<4<<" ";
for(int i=2;i<=n;i+=2){
if(i==4) continue;
else cout<<i<<" ";
}
cout<<"\n";
}
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}
//嘎嘎灵活的一道题：将除法和异或的性质结合
//直接遍历会超时，但是观察到因子的性质是小于等于被除数的一边
//异或是对二进制位进行操作，所以得到结论
//当y>2x的时候，（y^x）不可能是y或者x的因数，
//所以直接遍历就是可以
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ll x,m;
cin>>x>>m;
ll cnt=0;
for(ll i=1;i<=min(x*2,m);i++){
ll tmp=(i^x);
//cout<<tmp<<"ppppppp\n";
if(tmp==0) continue;
if(x%tmp==0||i%tmp==0) cnt++;
}
cout<<cnt<<"\n";
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}
超难，不写，但是有个有趣是：
x^y类似于不进位的加法，不借位的减法，有x-y<x^y<x+y
&是计算进位
//主意到n是奇数还是偶数最后一步的操作不同，同时最后一步奇数
//转化位偶数，注意到某数&n会小于等于n，|则是具有扩大性质
//观察样例发现，奇数个都满足=n，偶数打出二进制后发现都111
//所以可以得出凑1111，遇到&则会打回原型
//怎么构造11111呢
// 凑1.凑1111（n-1），n个1
// vector<int> s = {1, 3, h - 1, h, n};
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> per;
int last = -1;
if (n % 2 == 1) {
last = n;
n--;
}
int h = 1;
while (h * 2 <= n) {
h *= 2;
}
h -= 1;
for (int i = 1; i <= n; i++) {
if (i != 1 && i != 3 && i != (h - 1) && i != h && i != n) {
per.push_back(i);
}
}
// 凑1.凑1111（n-1），n个1
vector<int> s = {1, 3, h - 1, h, n};
if (h == 3) {
s = {2, 1, 3, n};
}
if (last!= -1) {
s.push_back(last);
}
for (int num : s) {
per.push_back(num);
}
if (last != -1) {
cout << last << "\n";
} else {
cout << (h * 2 + 1) << "\n";
}
for (int num : per) {
cout << num << " ";
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
//逆向思维一下，能出等于能进
#include <bits/stdc++.h>
using namespace std;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int cnt;
int n, m;
void dfs(string g[], vector<vector<int>>& vis, int x, int y) {
if (vis[x][y]||g[x][y]=='?') return;
vis[x][y] = 1;
cnt++;
if ( x + 1 < n&&g[x+1][y] == 'U') {
dfs(g, vis, x + 1, y);
}
if (y + 1 < m&&g[x][y+1] == 'L' ) {
dfs(g, vis, x, y + 1);
}
if ( x - 1 >= 0&&g[x-1][y] == 'D') {
dfs(g, vis, x - 1, y);
}
if ( y - 1 >= 0&&g[x][y-1] == 'R') {
dfs(g, vis, x, y - 1);
}
}
void solve() {
string g[n];
for (int i = 0; i < n; i++) {
cin>>g[i];
}
vector<vector<int>> vis(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
if (g[i][0] == 'L') dfs(g, vis, i, 0);
if (g[i][m-1] == 'R') dfs(g, vis, i, m - 1);
}
for (int i = 0; i < m; i++) {
if (g[0][i] == 'U') dfs(g, vis, 0, i);
if (g[n-1][i] == 'D') dfs(g, vis, n - 1, i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == '?') {
bool flag = true;
for (int k = 0; k < 4; k++) {
int nx = i + dx[k], ny = j + dy[k];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (!vis[nx][ny]) {
flag = false;
break;
}
}
if (flag) cnt++;
}
}
}
cout << (n*m-cnt) << "\n";
}
int main() {
int t;
cin >> t;
while (t--) {
cnt = 0;
cin >> n >> m;
solve();
}
}
//脑海闪过动态规划的状态机但是没有去做，但是时间复杂度显然正
//而且和之前设计过的某个状态（接龙序列很像）
//此题还有妙的解法，待开发
//dpi012，0代表无，1代表kip中，2代表已经skip了
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin>>n;
vector<int> vc(n);
for(int i=0;i<n;i++) cin>>vc[i];
vector<vector<int>> dp(n,vector<int>(3,0));
dp[0][0]=1;
dp[0][1]=0;
dp[0][2]=0;
for(int i=1;i<n;i++){
int c0=0,c2=0;
if(dp[i-1][0]<vc[i]) c0=1;
else if(dp[i-1][0]>vc[i]) c0=-1;
if(dp[i-1][2]<vc[i]) c2=1;
else if(dp[i-1][2]>vc[i]) c2=-1;
dp[i][0]=dp[i-1][0]+c0;
dp[i][1]=max(dp[i-1][0],dp[i-1][1]);
dp[i][2]=max(dp[i][1],dp[i-1][2]+c2);
}
cout<<dp[n-1][2]<<"\n";
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}
//我焯了，括号题，所有匹配题都可以想象成括号题，因为
//可以很方便的完成复杂的匹配
//这道题贪心的说就是
//要尽量两两一组，贵的免费，1可以当左括号也可以当右括号，但是0必须当左括号、、
//且0可以随意延申
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n;
cin>>n;
string s;
cin>>s;
deque<int> dq;
int sum=(n+1)*n/2;
for(int i=n-1;i>=0;i--){
if(s[i]=='1') dq.push_front(i+1);
else{
if(dq.size()){
sum-=dq.back();
dq.pop_back();
}
}
}
if(dq.size()){
int k=dq.size()/2;
while(k--){
sum-=dq.back();
dq.pop_back();
}
}
cout<<sum<<"\n";
}
signed main(){
int t;
cin>>t;
while(t--){
solve();
}
}
\\朴实无华的状态机，不用预处理，直接搞
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
vector<string>s(n);
vector<vector<int> >vot(2,vector<int>(n+8));
for(int k=0;k<2;k++)
{
cin>>s[k];
for(int i=0;i<n;i++)
if(s[k][i]=='A')
vot[k][i+1]=1;
}
vector<vector<int> >dp(n+9,vector<int>(3,-1));
dp[0][0]=0;
for(int k=0;k<=n-1;k++)
{
for(int i=0;i<3;i++)
{
if(dp[k][i]!=-1)
{
int vt=0,val=dp[k][i];
if(i==0)
{
vt=(vot[0][k+1]+vot[0][k+2]+vot[0][k+3])/2+(vot[1][k+1]+vot[1][k+2]+vot[1][k+3])/2;
dp[k+3][0]=max(vt+val,dp[k+3][0]);
vt=(vot[1][k+1]+vot[0][k+2]+vot[0][k+1])/2;
dp[k+1][1]=max(vt+val,dp[k+1][1]);
vt=(vot[1][k+1]+vot[1][k+2]+vot[0][k+1])/2;
dp[k+1][2]=max(vt+val,dp[k+1][2]);
}
if(i==1)
{
vt=(vot[0][k+2]+vot[0][k+3]+vot[0][k+4])/2+(vot[1][k+1]+vot[1][k+2]+vot[1][k+3])/2;
dp[k+3][1]=max(vt+val,dp[k+3][1]);
vt=(vot[1][k+1]+vot[1][k+2]+vot[0][k+2])/2;
dp[k+2][0]=max(vt+val,dp[k+2][0]);
}
if(i==2)
{
vt=(vot[1][k+2]+vot[1][k+3]+vot[1][k+4])/2+(vot[0][k+1]+vot[0][k+2]+vot[0][k+3])/2;
dp[k+3][2]=max(vt+val,dp[k+3][2]);
vt=(vot[0][k+1]+vot[0][k+2]+vot[1][k+2])/2;
dp[k+2][0]=max(vt+val,dp[k+2][0]);
}
}
}
}
cout<<dp[n][0]<<endl;
}
int main() {
int t;
cin>>t;
while(t--)
solve();
}
//这道题要看出奇偶的分段区别，偶数只有一种排法
//奇数根据数据范围和化成偶数需要双重循环分段
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
vector<int> vc(n);
for (int i = 0; i < n; i++) {
cin >> vc[i];
}
if(n==1){
cout<<1<<"\n";
return ;
}
map<int,int> mp;
if(n&1){
int mmin=1e18;
for(int i=0;i<n;i+=2){
for(int j=0;j<n-1;j++){
if(i==j) continue;
mp[vc[j+1]-vc[j]]++;
j++;
}
auto it=mp.rbegin();
mmin=min(mmin,it->first);
mp.clear();
}
cout<<mmin<<"\n";
}else{
for(int i=1;i<n;i+=2){
mp[vc[i]-vc[i-1]]++;
}
auto it=mp.rbegin();
cout<<it->first<<"\n";
}
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
//啊啊啊，这是拆位板子题。可恶想不到，
//首先&和|都是每位独立的运算，不进位和不退位
//关键观察到（a|b）-(a&c)整个式子也是每个二进制位独立的
//为什么呢，先固定a的某一位会发现|只是使之大于等于，&会使之小于等于
//所以做差后只会是10两种不会进位也不会退位
//所以可以拆位去计算每一位
//ps:观察数据结构发现是二进制题目，既然如此考
//虑拆位计算，但是担心进位退位就因该去验真
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int b,c,d;
cin>>b>>c>>d;
int ans=0;
for(int i=61;i>=0;i--){//组合起来八种情况干脆去枚举
int bitb=(b>>i)&1;
int bitc=(c>>i)&1;
int bitd=(d>>i)&1;
int wei=((int)1<<i);
if(bitb&&bitc&&bitd){
continue;
}else if(bitb&&!bitc&&bitd){
continue;
}else if(bitb&&bitc&&!bitd){
ans|=wei;
}else if(!bitb&&bitc&&bitd){
cout<<"-1\n";
return ;
}else if(!bitb&&!bitc&&bitd){
ans|=wei;
}else if(bitb&&!bitc&&!bitd){
cout<<"-1\n";
return ;
}else if(!bitb&&bitc&&!bitd){
continue;
}else if(!bitb&&!bitc&&!bitd){
continue;
}
}
cout<<ans<<"\n";
}
signed main(){
int t;
cin>>t;
while(t--){
solve();
}
}
// //解法1(异或前缀和；利用a^b^a=b得到suma^sum(n+1)=sum(a-b))
// //时间复杂度是n方
// #include <bits/stdc++.h>
// using namespace std;
// #define int long long
// void solve(){
// int n;
// cin>>n;
// vector<int> vc(n),sur(n+1);
// for(int i=0;i<n;i++) cin>>vc[i];
// sur[n-1]=vc[n-1];
// for(int i=n-2;i>=0;i--){
// sur[i]=sur[i+1]^vc[i];
// }
// int sum=0;
// for(int i=0;i<n-1;i++){
// for(int j=i+1;j<n;j++){
// sum+=sur[j+1]^sur[i];
// }
// }
// cout<<sum<<"\n";
// }
// signed main(){
// solve();
// }
//最优解法拆位：n
//前面二进制已经优化到了n方，其实对于公式还可以进一步与的化简
//设bi为数组的前缀异或，那么原式子可以理解为任意两两二元组
//bi的异或和，同时进一步化简会发现只有当1和0在一起的时候才会有
//贡献。利用乘法原理可得每一位的贡献就算cnt1*cnt0*2的权值
//（本题目规定长度至少是二所以记得减去sum）
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n;
cin>>n;
vector<int> vc(n+1);
int sum=0;
for(int i=1;i<=n;i++){
cin>>vc[i];
sum+=vc[i];
vc[i]^=vc[i-1];
}
int cnt_0,cnt_1;
int ans=0;
for(int i=0;i<=31;i++){
cnt_0=0;
cnt_1=1;//由于我们有一个额外的前缀 XOR 值 a[0] = 0，这意味着在统计 cnt0 时，初始就有一个前缀 XOR 值是 0，因此 cnt0 应该初始化为 1。
for(int j=1;j<=n;j++){
if((vc[j]>>i)&1){
cnt_1++;
}else{
cnt_0++;
}
}
ans+=(cnt_0)*(cnt_1)*(1<<i);
}
cout<<ans-sum<<"\n";
}
signed main(){
solve();
}
//误入dvi1.....
//Z函数，kmp待刷
//给你一个数c，你可以对一个数组任意加，求此时的最小差值，可以往余数上想，
//1数组中的ab，你可以通过调整加c的大小使得他们的差值是他们对c取余
//2如果给你的是两个数c，d，那么c和d不管怎么组合，都是gcd的倍数！！！
//3要特殊处理相邻两个的”余数互补情况“，比如余1 和 5 ，st是8，那么可以对1+6
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while(T--){
ll n, a, b;
cin >> n >> a >> b;
ll d = gcd(a, b);
vector<ll> A(n);
for(int i = 0; i < n; ++i){
cin >> A[i];
A[i] %= d;
}
sort(A.begin(), A.end());
ll res = A[n-1] - A[0];
for(int i = 1; i < n; ++i){
res = min(res, A[i-1] + d - A[i]);
}
cout << res << "\n";
}
return 0;
}
//这道题标准答案是利用了背包的思想，但是我感觉普通的线性枚举也可以实现（日后实现，卡住了）
//状态设计dpik，i表示到第i个字符，j表示匹配了前narek的前k个
//状态转移：dp i+1 knext=dpi，k+sorck,刷表法
//初始条件：dp 0 0=0,其他-2e9
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
string ta="narek";
pii get(string s,int now){
int ans=0;
for(auto c:s){
if(c==ta[now]){
now++;
if(now==5){
ans+=10;
now=0;
}
}
if(ta.find(c)!=-1) ans--;
}
return {now,ans};
}
void solve(){
int n,m;
cin>>n>>m;
string s[n];
for(int i=0;i<n;i++) cin>>s[i];
vector<vector<int>> dp(n+1,vector<int>(5,-2e9));
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int k=0;k<5;k++){
dp[i][k]=max(dp[i][k],dp[i-1][k]);//选不选这个组
pii a=get(s[i-1],k);
dp[i][a.first]=max(dp[i][a.first],dp[i-1][k]+a.second);
}
}
int mamx=0;
for(int i=0;i<5;i++) mamx=max(mamx,dp[n][i]);
cout<<mamx<<"\n";
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}
//错误代码
// #include <bits/stdc++.h>
// using namespace std;
//
// void solve(){
// int n,m;
// cin>>n>>m;
// string s[n];
// for(int i=0;i<n;i++) cin>>s[i];
// vector<vector<vector<int>>> dp(n,vector<vector<int>>(m,vector<int>(5)));
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// if(i){
// dp[i][j][0]=dp[i-1][j][1];
// dp[i][j][1]=dp[i-1][j][1];
// dp[i][j][2]=dp[i-1][j][2];
// dp[i][j][3]=dp[i-1][j][3];
// dp[i][j][4]=dp[i-1][j][4];}
// int tag=-1;
// if(s[i][j]!='n'&&s[i][j]!='a'&&s[i][j]!='r'&&s[i][j]!='e'&&s[i][j]!='k') tag=0;
//
// if(i){
// dp[i][j][0]=max(dp[i-1][m-1][4]+s[i][j]=='n'?2:tag,dp[i][j][0]);
// dp[i][j][1]=max(dp[i-1][m-1][0]+s[i][j]=='a'?2:tag,dp[i][j][1]);
// dp[i][j][2]=max(dp[i-1][m-1][1]+s[i][j]=='r'?2:tag,dp[i][j][2]);
// dp[i][j][3]=max(dp[i-1][m-1][2]+s[i][j]=='e'?2:tag,dp[i][j][3]);
// dp[i][j][4]=max(dp[i-1][m-1][3]+s[i][j]=='k'?2:tag,dp[i][j][4]);}
//
// if(j)dp[i][j][1]=max(dp[i][j-1][0]+s[i][j]=='a'?2:tag,dp[i][j][1]);
// if(j)dp[i][j][2]=max(dp[i][j-1][1]+s[i][j]=='r'?2:tag,dp[i][j][2]);
// if(j)dp[i][j][3]=max(dp[i][j-1][2]+s[i][j]=='e'?2:tag,dp[i][j][3]);
// if(j)dp[i][j][4]=max(dp[i][j-1][3]+s[i][j]=='k'?2:tag,dp[i][j][4]);
// }
//
// }
// cout<<dp[n-1][m-1][4]<<"\n";
// }
// int main(){
// int t;
// cin>>t;
// while(t--){
// solve();
// }
// }
//
//看了答案后一知半解的解法
//对于周期性，取模的应用，发现a到a+k，a+2k到a+3k，所以规律是
//（（a）%（2k））~((a+k-1)%2k)(注意当前者大于后者的时候，记得区间绕)
//所以就是求这些线段的最早交点（满足n个）。
//那么要怎么构造这个最早的答案，首先ans>=max（a）
//其次由于周期性，其实ans只在max（a）的第一个k区间里面
//我们只需要通过枚举开头mmax+abs（r-max（a）%2k）就可以
//r在0到2k
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n,k;
cin>>n>>k;
vector<int> vc(n);
vector<int> dc(2*k+1);
int mmax=0;
for(int i=0;i<n;i++) {
cin>>vc[i];
mmax=max(mmax,vc[i]);
int l=vc[i]%(2*k);
int r=(vc[i]+k-1)%(2*k);
if(l<r){
dc[l]++;
dc[r+1]--;
}else{
dc[l]++;
dc[0]++;
dc[r+1]--;
}
}
if(n==1){
cout<<mmax<<"\n";
return ;
}
int ans=2e9;
for(int i=0;i<2*k;i++){
if(i) dc[i]+=dc[i-1];
if(dc[i]!=n) continue;
if(i >= mmax % (2 * k)){
ans = min(ans, (mmax - (mmax % (2 * k)) + i));
}
else{
ans = min(ans, (mmax - (mmax % (2 * k)) + i+ 2 * k));
}
}
if(ans>=2e9){
cout<<-1<<"\n";
}else{
cout<<ans<<"\n";
}
}
signed main(){
int t;
cin>>t;
while(t--){
solve();
}
}
//一开始我就是这样子想的，这也但是没有实现，这个写的太庙了
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
typedef long long ll;
ll a[maxn], b[maxn];
int n;
void solve() {
long long n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
int diff = a[n] - a[i];
a[i] += diff / (2 * k) * (2 * k);
if (a[i] + k < a[n]) a[i] += 2 * k;
}
sort(a + 1, a + 1 + n);
if (a[n] - a[1] < k) cout << a[n] << endl;
else cout << -1 << endl;
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
}
//这种题真的想得出来吗，好吧吸取教训，如果有一个想法就要去验证看看
//这道题关于”对称减“，观察样例发现样例奇偶同时出现有奇怪
//思考。如果数组同时存在奇数和偶数的话，那么这个x不管是奇数还是偶数都不会产生单一的奇偶
//其次，要思考怎么构造四十个数以内来去实现这个变为0，我的想法是通过gcd，但是gcd次数太多
//答案显示，通过2的幂每次来二分区间，由于每个数小于2的三十次方，从2的30幂开始，对称减法，发现
//下一次的数都小于2的30次方，然后用2的29次方依次类推，最后变成1或者0，如果全是1显然是正确的
//01交错就是-1；（然而这种情乱不可能同时出现，由于上面都是二的幂次操作，所以剩余1就是全偶数，全奇数就是剩余0）
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin>>n;
vector<int> vc(n);
bool a=false,b=false;
for(int i=0;i<n;i++){
cin>>vc[i];
if(vc[i]&1){
b=true;
}else{
a=true;
}
}
if(a&&b){
cout<<-1<<"\n";
return ;
}
if(a){
cout<<31<<"\n";
}else{
cout<<30<<"\n";
}
for(int i=29;i>=0;i--){
cout<<(1<<i)<<" ";
}
if(a) cout<<1;
cout<<"\n";
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}
//观察发现经过一次操作后数组，变成递增，且为相同的相邻
//但是此时结构还是混乱的，比如会出现（2）（1）（2），（1）（1）（1），（2）（2）（1）的混乱
//但是在进行一次操作就全都会变成有序（多）（多）（单或多）
//此时就可以完美经经行以下操作了
//发现后续贡献操作是有两个以上的右移动，且增加，单个的贡献完就消失
//多次操作后让数组变得有序(依稀记得之前有一道题也是要两次操作才会让数组变得规律)
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n;
cin>>n;
vector<int> vc(n);
int mmax=0;
map<int,int> mp;
int sum=0;
for(int i=0;i<n;i++) {
cin>>vc[i];
mp[vc[i]]++;
if(mp[vc[i]]>=2){
mmax=max(mmax,vc[i]);
}
sum+=vc[i];
vc[i]=mmax;
}
mmax=0;
mp.clear();
for(int i=0;i<n;i++) {
mp[vc[i]]++;
if(mp[vc[i]]>=2){
mmax=max(mmax,vc[i]);
}
sum+=vc[i];
vc[i]=mmax;
}
for(int i=n-1;i>=0;i--){
sum+=vc[i]*(n-i);
}
cout<<sum<<"\n";
}
signed main(){
int t;
cin>>t;
while(t--){
solve();
}
}
//这道题的思想，之前我记得有做过类似的，对于线段这种处理，就算有前缀和暴力就是枚举（len和起点i）n方
//但是根据本题是要找出和为0，那么可以利用map的思想，去找前面的，线性计算
//同时要用数组模拟map不然会超时，因为此时的贡献计算方式可以化成
//
// ans += (sum_map[pre[y] + offset] * (n - y + 1)) % MOD;//每次计算最右边的l和最左边的r，保证不重复；
// ans %= MOD;
//
// sum_map[pre[y] + offset] += (y +1);//直接相加了就好，因为都是乘以0到i
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
void solve(){
string s;
cin >> s;
int n = s.size();
vector<int> pre(n + 1, 0);
vector<long long> sum_map(2*n + 1, 0);
int offset = n;
sum_map[pre[0] + offset] += 1;
int ans = 0;
for(int y =1; y <=n; y++){
if(s[y-1] == '1')
pre[y] = pre[y-1] + 1;
else
pre[y] = pre[y-1] - 1;
ans += (sum_map[pre[y] + offset] * (n - y + 1)) % MOD;//每次计算最右边的l和最左边的r，保证不重复；
ans %= MOD;
sum_map[pre[y] + offset] += (y +1);//直接相加了就好，因为都是乘以0到i
sum_map[pre[y] + offset] %= MOD; // 防止溢出
}
cout << ans % MOD << "\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--){
solve();
}
}
//纯数学分析题，放缩，属于是高中知识不过关
//首先对于ab+bc+ac<=n,除以a关注b得到，当a=1，b有n个选择，当a=2，有n/2.。。。
//调和数列，有nlogn个，所以可以循环ab
//有了a和b后就只需要考虑c了，对于不等式2，就是c《=x-a-b
//所以维护一个min（不等式1，不等式2）就可以
#include <bits/stdc++.h>
using namespace std;
int main(){
int tc;
cin >> tc;
while (tc--){
int n, x;
cin >> n >> x;
long long ans = 0;
for (int a = 1; a <= min(n, x); a++){
for (int b = 1; a * b <= n and a + b <= x; b++){
int highestC = min((n - a * b) / (a + b), x - (a + b));
ans += highestC;
}
}
cout << ans << "\n";
}
}
//久违的水题，爽，
//每次选电影的时候的分类讨论对贡献的影响就行，保证两种平均且大
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
void solve(){
int n;
cin>>n;
int cnt1=0;
int cnt2=0;
int a=0,b=0;
vector<pii> vc(n);
for(int i=0;i<n;i++){
cin>>vc[i].x;
}
for(int i=0;i<n;i++){
cin>>vc[i].y;
}
for(auto [i,j]:vc){
if(i==-1&&j==-1){
cnt1++;
}else if(i==1&&j==1){
cnt2++;
}else{
if(i>j){
a+=i;
}else{
b+=j;
}
}
}
int mmin=min(a,b),mmax=max(a,b);
if(cnt1>mmax-mmin){
cnt1-=(mmax-mmin);
mmax=mmin;
cnt2-=cnt1;
if(cnt2>0){
cout<<(mmax+cnt2/2)<<"\n";
}else{
cout<<(mmax+(cnt2-1)/2)<<"\n";
}
}else{
mmax-=cnt1;
if(cnt2>mmax-mmin){
cnt2-=(mmax-mmin);
mmin=mmax;
cout<<mmax+(cnt2)/2<<"\n";
}else{
cout<<mmin+cnt2<<"\n";
}
}
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}
C
（待补）
//能转化为背包dp的是这个（大拇指），我是这个（倒拇指）
//首先明确，博弈规则：a从小到大拿，b优先拿在时效性内代价小的
//排序贪心失败，但是可以贪心：首先将蛋糕预处理成价值1，代价（cnt）
//其次进行dp，dp是让a拿最少（因为a的博弈策略简单）
//状态设计：第i个，代价j的范围内
//奇怪的背包还没理解
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
void solve(){
int n;
cin>>n;
map<int,int> mp;
int num;
for(int i=0;i<n;i++){
cin>>num;
mp[num]++;
}
int sz=mp.size();
vector<int> a(sz+1);
int cnt=1;
for(auto [i,j]:mp){
a[cnt++]=j;
}
vector<vector<int>> dp(sz+1,vector<int>(sz+2,0));
for(int i=2;i<=sz;i++){
for(int j=0;j<i;j++){
dp[i][j+1]=dp[i-1][j+1];（j+1是为了保证a下了，防止连续b下大于a的下次数
1. ）
if(j>=a[i])dp[i][j+1]=max(dp[i-1][j-a[i]]+1,dp[i][j+1]);
}
}
int mmax=0;
for(int i=0;i<=sz;i++){
mmax=max(dp[sz][i],mmax);
}
cout<<sz-mmax<<"\n";
}
//2 6 5 3 9 1 6 2 5 6 3 2 3 9 6 1 6
//1 1 2 2 2 3 3 3 5 5 6 6 6 6 6 9 9
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}
///为什么这个递推是正确的呢
//因为保证了a和b次数的平衡
const ll maxn=5005;
ll f[maxn][maxn];
ll a[maxn],tot,b[maxn];
ll n;
ll dfs(ll x,ll t){//记忆化搜索
if(x>tot)return 0;
if(~f[x][t])return f[x][t];
ll res=dfs(x+1,t+1)+1;
if(t>=b[x])res=min(res,dfs(x+1,t-b[x]));
return f[x][t]=res;
}
void solve(){
n=R;
tot=0;
for(ll i=1;i<=n;i++){
a[i]=R;
for(ll j=0;j<=n;j++)f[i][j]=-1;//多测清空
}
sort(a+1,a+1+n);
for(ll i=1;i<=n;i++){
if(a[i]>a[i-1])b[++tot]=1;
else b[tot]++;
}//合并
we(dfs(1,0));
return ;
}
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,T,a[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int k=0;
for(int i=1;i<=n;i++)k=max(a[i]+i,k);
cout<<k-1<<"\n";
}
return 0;
}
屎删代码，分类讨论加组内排序二分
