A.Indirect Sort
首先，如果\(a_i>a_k\),\(a_i\)就会变大，而这样的操作是没有意义的.
因此操作可以转换为\(\forall j,k(j<k)\), 如果\(\exists i,i<j\),使得\(a[i]<=a[k]\), 则交换\(a[j],a[k]\)
注意到当‘1’不是第一个数时，无论如何都无法将'1'交换，为‘NO'.
而当'1'为第一个数时，可以使所有操作中i=1,那么后面的数可以任意交换，意味着序列可以排序，为’YES'.
#define DEBUG 0
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,a,b) for (int i=a;i>=b;i--)
#define ll long long
#define eb emplace_back
int t,n,a;
using namespace std;
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
bool fl=0;
scanf("%d",&a);
if (a==1) fl=1;
for (int i=2;i<=n;i++)
scanf("%d",&a);
if (fl) printf("YES\n");
else printf("NO\n");
}
#if DEBUG
system("pause");
#endif
return 0;
}
B.Maximum Substring
-
对于\(x*y\)的计算方法 ，必定要使得\(x,y\)尽可能大.选择整个序列即可.
-
对于\(x^2\),\(y^2\),选择最长的连续0/1串.一遍扫过去.
#define DEBUG 0 #include <bits/stdc++.h> #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,a,b) for (int i=a;i>=b;i--) #define ll long long #define eb emplace_back using namespace std; int t,n; char s[200010]; int main() { scanf("%d",&t); while (t--) { scanf("%d %s",&n,s+1); int sumx=0,sumy=0,nwx=0; char nw='9'; ll ans=0; for (int i=1;i<=n;i++) { if (s[i]=='1') sumx++; else sumy++; if (s[i]!=nw) { ans=max(ans,1ll*nwx*nwx); nw=s[i]; nwx=1; } else nwx++; } ans=max(max(ans,1ll*sumx*sumy),1ll*nwx*nwx); printf("%lld\n",ans); } #if DEBUG system("pause"); #endif return 0; }
C.Complementary XOR
构造题.
因为操作对于a,b序列完全相反，手玩一下发现只有a,b相同或相反时才可做.
如果a,b完全相反则可以对a做一次[1,n]的操作，变成完全相同 .
当a,b完全相同时，为0的地方不用管.
设\(s1[i]=s2[i]=1\)
若\(i=1\) 可以进行\([1,n]\),\([2,n]\)操作，这样可以只修改i位置上的数
若\(i>1\)同理，进行\([1,i-1]\),\([1,i]\)操作.
用栈维护一下，去除相同操作.
#define DEBUG 0
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define N 200010
using namespace std;
int t,n,cnt;
char s1[N],s2[N];
pair <int,int> ans[N];
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%d %s %s",&n,s1+1,s2+1);
bool fl=1;
rep(i,1,n)
{
if ((s1[i]==s2[i]) != (s1[1]==s2[1]))
{
printf("NO\n");
fl=0;
break;
}
}
if (fl==0) continue;
printf("YES\n");
cnt=0;
if (s1[1]!=s2[1])
{
ans[++cnt]={1,n};
rep(i,1,n) s1[i]=((s1[i]=='1')?'0':'1');
}
if (s1[1]=='1') ans[++cnt]={2,n},ans[++cnt]={1,n};
rep(i,2,n)
if (s1[i]=='1')
{
if (ans[cnt]==make_pair(1,i-1))
{
cnt--;
ans[++cnt]={1,i};
}
else
{
ans[++cnt]={1,i-1};
ans[++cnt]={1,i};
}
}
printf("%d\n",cnt);
rep(i,1,cnt)
printf("%d %d\n",ans[i].first,ans[i].second);
}
#if DEBUG
system("pause");
#endif
}
D.Count GCD
注意到若\(a[i-1]\nmid a[i]\)则必定不可行.
设\(f[i]\)表示到\(i\)时的答案.
\(pw\)等于所有\(s\in[1,m],gcd(a[i-1],s)=a[i]\)的数量
则\(f[i]=f[i-1]*pw\)
设\(s=k*a[i]\)
上式化为\(gcd(a[i-1]/a[i],k)=1,k\in[1,\lfloor m/a[i]\rfloor]\)
容斥一下即可
#define DEBUG 0
#include <bits/stdc++.h>
#define N 200010
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define eb emplace_back
#define ll long long
#define P 998244353
using namespace std;
int t,n,a[N],m,tans;
vector <int> fc;
int qpow(int x)
{
if (x&1) return -1;
return 1;
}
void dfs(int num,int dep,int n,int pw)
{
pw*=fc[num];
tans+=qpow(dep)*(n/pw);
rep(i,num+1,(int)fc.size()-1)
dfs(i,dep+1,n,pw);
}
ll getans(int p,int n,vector <int> a)
{
fc.clear();
for (auto v:a)
if (p%v==0)
fc.eb(v);
tans=n;
rep(i,0,(int)fc.size()-1)
dfs(i,1,n,1);
return tans;
}
int main()
{
#if DEBUG
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
#endif
scanf("%d",&t);
while (t--)
{
scanf("%d %d",&n,&m);
bool ok=1;
rep(i,1,n)
{
scanf("%d",&a[i]);
if (a[i-1]%a[i]!=0) ok=0;
}
if (!ok)
{
printf("0\n");
continue;
}
vector <int> fac;
int tp=a[1];
for (int i=2;i*i<=a[1];i++)
{
if (tp%i==0)
fac.eb(i);
while (tp%i==0) tp/=i;
}
if (tp>1) fac.eb(tp);
ll ans=1ll;
rep(i,2,n)
ans=(ans*getans(a[i-1]/a[i],m/a[i],fac))%P;
printf("%lld\n",ans);
}
#if DEBUG
system("pause");
#endif
return 0;
}
E.Bracket Cost
考虑对于一个子串应该怎么处理
设该子串中左括号的数量为\(L\)，右括号的数量为\(R\)，完全匹配对数为\(X\)
结论：操作次数为\(max(L,R)-X\)
证明：去掉所有已经匹配的字符，子串必定化为这种形式——))...)((...((
不妨设左括号数量更多，匹配方式：把\(R-X\)个左括号移动到与右括号匹配，再添加\(L-R\)个右括号.
计算\(\Sigma max(L,R)和\Sigma X\)即可.
后者使用栈是好求的.
前者需要一点变换.
\(max(L,R)\)可以变为\((R+L+|R-L|)/2\)，再分开计算\(R+L\),\(|R-L|\)
前者好求
难求的是绝对值.
将'('看作1，')'看作-1，做一次前缀和.
对于某一个区间，\(|R-L|=|sum_R-sum_L|\)
\(Sum=\Sigma_{i=0}^{n-1}\Sigma_{j=i+1}^nsum_j-sum_i\)
将sum升序排序即可计算全部的值.
#define DEBUG 0
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define N 200010
#define ll long long
using namespace std;
int t,n,sum[N];
char s[N];
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%d %s",&n,s+1);
ll ans=0;
stack <int> q;
rep(i,1,n)
{
if (s[i]=='(')
q.push(i);
else if (q.size())
{
ans-=1ll*q.top()*(n-i+1);
q.pop();
}
}
ll tp=0;
rep(i,1,n)
{
if (s[i]=='(')
sum[i]=sum[i-1]+1;
else sum[i]=sum[i-1]-1;
}
rep(i,1,n)
tp+=1ll*i*(n-i+1);
sort(sum,sum+n+1);
rep(i,1,n) tp+=1ll*sum[i]*i;
rep(i,0,n-1) tp-=1ll*sum[i]*(n-i);
tp/=2;
printf("%lld\n",tp+ans);
}
#if DEBUG
system("pause");
#endif
return 0;
}