Contest Link Official Editorial
给你一个数 \(n\) ,每一步可以做以下两个操作之一:
问变成 \(1\) 的最小步数。
又是赛时乱搞……赛时一开始写了一个除了质数以外能除就除的东西,然后交上去 Wa on 2
;于是又加了一个奇数就减偶数就除的东西,两个取 \(\min\) ,就过了……(其实这个想法貌似就是正解……当时还挺担心会被 Hack )
如果 \(n\leq 3\) ,直接输出答案。
否则,如果 \(n\) 是奇数,那么 n-1
是偶数,然后可以直接变成 \(2\) ,答案是 \(3\) .
如果 \(n\) 是偶数,那就直接变 \(2\) ,答案是 \(2\) .
//Author: RingweEH
int find( int x )
{
int lim=sqrt(x);
for ( int i=2; i<=lim; i++ )
if ( x%i==0 ) return x/i;
return -1;
}
int main()
{
int T=read();
while ( T-- )
{
int n=read(),sav=n; int cnt=0;
while ( n!=1 )
{
cnt++; int x=find(n);
if ( x==-1 ) n--;
else n/=x;
}
int cnt2=0; n=sav;
while ( n!=1 )
{
cnt2++; int x=find(n);
if ( (n&1) || (x==-1) ) n--;
else n/=x;
}
printf( "%d\n",min(cnt,cnt2) );
}
}
给定一个长度为 \(n\) 的01串 \(s\) 和 \(q\) 个询问。每个询问形如 \(l_i,r_i\) 要求:
问是否存在这样的子序列。
其实想一下就会发现,如果找不到,那么肯定只有 \([l_i,r_i]\) 这一个连续的子序列。
如果找到了,说明至少能把 \([l_i,r_i]\) 的头往前移或者把尾往后移。(因为 \([l_i,r_i]\) 是相邻的,要是能移动肯定是满足能移动头尾的)
所以判断 \(s[1,l_i-1]\) 中是否存在 \(s[j]=s[l_i]\) 即可,\(r_i\) 同理。
//Author: RingweEH
int l=read(),r=read(); bool fl=0;
for ( int i=1; i<l; i++ )
if ( s[i]==s[l] ) fl=1;
for ( int i=n; i>r; i-- )
if ( s[i]==s[r] ) fl=1;
fl ? printf( "YES\n" ) : printf( "NO\n" );
给定两个由小写英文字符组成的字符串 \(a,b\) .对 \(a\) 可以进行两个操作:
问能否把 \(a\) 变成 \(b\) .
能交换字符说明不需要考虑顺序问题。记 \(cnta[c],cntb[c]\) 为 \(c\) 在 \(a,b\) 中出现的次数。
由题目可知,如果要改变字符只能变大不能变小。
所以正序扫一遍这两个数组,
//Author: RingweEH
n=read(); k=read(); scanf( "%s",sa ); scanf( "%s",sb );
for ( int i=0; i<n; i++ )
cnta[sa[i]-'a']++,cntb[sb[i]-'a']++;
int cntk=0; bool fl=1;
for ( int i=0; i<25; i++ )
{
if ( cnta[i]>=cntb[i] )
{
if ( ((cnta[i]-cntb[i])%k)!=0 ) { fl=0; break; }
cntk+=(cnta[i]-cntb[i])/k;
}
else
{
if ( ((cntb[i]-cnta[i])%k)!=0 ) { fl=0; break; }
int del=(cntb[i]-cnta[i])/k;
if ( del>cntk ) { fl=0; break; }
cntk-=del;
}
}
if ( fl ) printf( "Yes\n" );
else printf( "No\n" );
\(\text{Ashish}\) 先手,\(\text{Utkarsh}\) 后手。
在一个二维平面上,有一个棋子被放在 \((0,0)\) 处。每一步移动可以让 \(x\) 或者 \(y\) 坐标增加 \(k\) ,且每一步必须在以 \((0,0)\) 为圆心, \(d\) 为半径的圆内。不能移动判负。问谁必胜。
显然,一开始只要 \(Ashish\) 能动,\(Utkarsh\) 都能在另一维坐标上相应移动。最后会到达点 \((k\times z,k\times z)\) 。
这时候,如果 \((k\times z,k\times (z+1))\) 在圆内,那么先手胜;否则后手胜。
//Author: RingweEH
ll d=read(),k=read(),z=1;
while ( sqr(z*k)*2<=sqr(d) ) z++; z--;
if ( sqr(z*k)+sqr(z*k+k)<=sqr(d) ) printf( "Ashish\n" );
else printf( "Utkarsh\n" );
交互题。有三种询问形式:
AND i j
: \(a_i \& a_j\)OR i j
: \(a_i|a_j\)XOR i j
: \(a_i\oplus a_j\)保证 \(a_i\in[0,n-1]\) 。要求在不超过 \(n+1\) 次询问中得到整个序列。
分两种情况讨论。首先,\(n-1\) 次询问 \(a[1]\oplus a[i]\) .
//Author: RingweEH
int get_query( int opt,int x,int y )
{
if ( opt==1 ) cout<<"AND "<<x<<" "<<y<<endl;
else if ( opt==2 ) cout<<"OR "<<x<<" "<<y<<endl;
else if ( opt==3 ) cout<<"XOR "<<x<<" "<<y<<endl;
cout.flush(); int tmp; cin>>tmp; return tmp;
}
int main()
{
cin>>n; sum[0]=1; int id=0;
for ( int i=2; i<=n; i++ )
{
int tmp=get_query( 3,1,i ); ans[i]=tmp;
if ( !sum[tmp] ) sum[tmp]=i;
else id=i;
}
if ( id )
{
int tmp=get_query( 1,sum[ans[id]],id );
ans[1]=ans[id]^tmp;
for ( int i=2; i<=n; i++ )
ans[i]^=ans[1];
}
else
{
int t1=get_query(1,sum[1],1),t2=get_query(1,sum[2],1);
int tmp=t1+t2%2;
for ( int i=1; i<=n; i++ )
ans[i]^=tmp;
}
cout<<"! ";
for ( int i=1; i<=n; i++ )
cout<<ans[i]<<' ';
return 0;
}
给定一个 \(n\times m\) 的矩阵,元素为非负数。轮流操作:
当矩阵的数全部为 0 时,无法操作的一方输。问胜者。
结论:
令常数 \(d\) 为斜对角线上 \(r,c\) 坐标之和,\(xor(d)=a_{r_1,c_1}\oplus a_{r_2,c_2}\oplus…\oplus a_{r_n,c_n}(r_i+c_i==d)\) 。
如果对于所有的 \(d\) ,在游戏开始时有 \(xor(d)=0\) ,那么后手胜,否则先手必胜。(深刻感受到翻译的痛苦)
Let's consider diagonals \(d\) of the form \(r+c\) - the diagonals where the sum of row index (r) and column index (c) is constant. Then xor of a diagonal \(d\) will be \(xor(d)=a(r1,c1)⊕a(r2,c2)⊕…a(rn,cn)\) , such that \(r_1+c_1=d\) , \(r_2+c_2=d\) , …. \(r_n+c_n=d\) .
If \(0∀d,xor(d)=0\) at the start of the game, then Jeel wins. Else, Ashish wins.
\(Proof\) :设状态 \(S_1\) 为对于任意的 \(d\) ,\(xor(d)=0\) ;设状态 \(S_2\) 为存在 \(d\) 使得 \(xor(d)\neq 0\) .
\(Lemma1\) :对 \(S_1\) 中状态进行的任何操作都将转移到 \(S_2\) .由于起点不能在路径中被改变且在开头必须被改成一个 \([0,a_{r_1,c_1}-1]\) 之间的数,所以异或和一定不为0.
\(Lemma2\) :永远存在一种转移使得 \(S_2\) 中的状态能转移到 \(S_1\) 中。对于一个状态,如果其异或值不为 0 ,总能选择一个数,让它变小之后异或值为 0 .
发现 \(S_1\) 属于败集。那么如果初始状态属于 \(S_2\) ,先手就总能把败局留给后手,而后手只能把胜局留给先手。
复杂度 \(\mathcal{O}(n\times m)\) .
//Author: RingweEH
int main()
{
int T=read();
while ( T-- )
{
memset( sum,0,sizeof(sum) );
n=read(); m=read();
for ( int i=1; i<=n; i++ )
for ( int j=1; j<=m; j++ )
{
a[i][j]=read(); sum[i+j]^=a[i][j];
}
bool fl=1;
for ( int i=1; i<=n+m; i++ )
fl&=(sum[i]==0);
if ( !fl ) printf( "Ashish\n" );
else printf( "Jeel\n" );
}
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章