30 条题解
-
4
lxy8584099 LV 7 @ 2018-08-22 17:17:12
#include<cstdio> #define ll long long using namespace std; const int N=100100; int n,a[2][N],ans[N<<1],k; ll m; int main() { int i,j; scanf("%d%lld",&n,&m); for(i=1;i<=n;i++) scanf("%d",&a[0][i]),a[0][i]--; for(j=1;(1LL<<j)<=m;j++) // 处理第 2^j 那一次变化 { if(m&(1LL<<j)) { ll l=(1LL<<j); for(i=1;i<=n;i++) { int x=(i-(l>>1)%n+n-1)%n+1; // i 左边第 2^(j-1) 个数字 int y=(i+(l>>1)%n+n-1)%n+1; // i 左边第 2^(j+1) 个数字 a[k^1][i]=a[k][x]^a[k][y]; }k^=1; } } for(i=1;i<=n;i++) ans[(i<<1)-1]=a[k][i]; //先后先放在奇数位 if(m&1) // 处理 2^0 变化 { for(i=1;i<=n;i++) ans[i<<1]=ans[i+i-1]^ans[i==n?1:i<<1|1]; for(i=1;i<=n;i++) ans[i+i-1]=-1; // 把不需要的奇数位变成 0 } else for(i=1;i<=n;i++) ans[i+i]=-1; // 把不需要的偶数位变成 0 for(i=1;i<=(n<<1);i++) printf("%d%c",ans[i]+1,i==(n<<1)?'\n':' '); // 注意还原题意 （ ans+1 ） return 0; } // 第2^k行每个数是原序列该位置左侧第2^(k-1)个数和右侧第2^(k-1)个数的异或-
太好了
-
-
3
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<string> #include<cstring> #define inf 1e9 #define ll long long #define For(i,j,k) for(ll i=j;i<=k;i++) #define Dow(i,j,k) for(ll i=k;i>=j;i--) using namespace std; ll a[500001],t[500001],n,T; inline ll get(ll x,ll dlt) { ll l=((x-dlt)%(n*2)+n*2-1)%(n*2)+1,r=((x+dlt)-1)%(n*2)+1; if(!a[l]) return 0; if(a[l]==a[r]) return 1;else return 2; } inline void ksm(ll x,ll dlt) { if(x==0) return; ksm(x/2,dlt<<1); if(x%2) { For(i,1,2*n) t[i]=0; For(i,1,2*n) t[i]=get(i,dlt); For(i,1,2*n) a[i]=t[i]; } } int main() { scanf("%d%lld",&n,&T); For(i,1,n) scanf("%d",&a[2*i-1]); ksm(T,1); For(i,1,2*n) printf("%d ",a[i],i); }-
njnu19180103 @ 2020-02-06 10:12:38
要是有注释就更好了>.<
-
-
2
问题分析
一串数字的T次同或操作。
重点
1.该桌是一个圆桌，因此首尾相邻
2.每一次操作，所有间隙值都要改变
3.值2即相当于逻辑运算中的0
4.( site )( 2^m )=( site - 2^(m - 1) )( 0 ) xnor ( site + 2^(m - 1) )( 0 )
即 2^m 次操作之后 site 位置的值
=当前 site - 2^(m - 1) 位置和 site + 2^(m - 1) 位置的值的 同或.数据结构
1.T非常大必须用long long int储存
2.n个数据可以用字符数组、整形数组储存
3.新建一个数组来保存中间值算法分析
1.找到一个m使 2^m <= T
2.首先运用刚刚的规律进行 2^m 次操作，得到奇数位数据
3.运算了 2^m 次操作 之后, T = T - 2^m
重复上述三个步骤，直到T <= 1
4.若T此时为1，则再进行一次操作，得到偶数位数据下面给出代码:
#include<iostream> #include<cmath> using namespace std; int main() { long long int n, T; int coin[100000], _coin[100000]; cin >> n >> T; long long int _T = T; int m; T = T - T % 2; for (long long int i = 0; i < n; i++) { cin >> coin[i]; _coin[i] = coin[i]; }//输入数据 for (m = 0; (long long int)pow(2, m) <= T; m++); for (m--; T != 0; m--) {//2次方操作 T -= (long long int)pow(2, m); for (long long int i = 0; i < n; i++)//进行2^m次操作 { long long int a = i - (long long int)pow(2, m - 1); if (coin[a < 0 ? (n + a % n) % n : a] == \ coin[(i + (long long int)pow(2, m - 1)) % n]) _coin[i] = 1; else _coin[i] = 2; } for (long long int i = 0; i < n; i++)coin[i] = _coin[i]; for (m = 0; pow(2, m) <= T; m++); } if (_T % 2 != 0) {//若T为奇数,则多进行一次操作 for (long long int i = 0; i < n; i++)coin[i] = _coin[i]; for (long long int i = 0; i < n - 1; i++) { if (coin[i] == coin[i + 1])_coin[i] = 1; else _coin[i] = 2; } if (coin[0] == coin[n - 1])_coin[n - 1] = 1; else _coin[n - 1] = 2; } if (_T % 2 == 0)for (int i = 0; i < n; i++)cout << _coin[i] << " 0 ";//输出 else for (int i = 0; i < n; i++)cout << "0 " << _coin[i] << " "; return 0; } -
1
-
0
xianggulinger LV 8 @ 2017-09-26 19:42:47
快速幂。
```cpp
#include <iostream>
#include <vector>
#include <iterator>
#include <set>
#include <algorithm>
typedef long long ll;
#define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
#define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)
#define ff(i) For(i, 0, 2 * n - 1)using namespace std;
int co[300000];
int co2[300000];
ll t;
int n;int DA[300000];
int P2N[300000];int da(int x){
return ((x + 10 * n) % (2 * n));
}void up0(){
For(i, 0, 2 * n - 1){
if (co[i] != 0){
co2[i] = 0;
} else{
co2[i] = co[da(i - 1)] * co[da(i + 1)];
}
}
For(i, 0, 2 * n - 1){
co[i] = co2[i];
}
}int p2n(int x){
if (P2N[x] != 0){
return P2N[x];
}
if (x == 1){
return P2N[x] = (2 % (2 * n));
}
return P2N[x] = ((p2n(x - 1) * 2) % (2 * n));
}void up(int x){
if (x != 0) {
For(i, 0, 2 * n - 1) {
if (co[i] == 0) {
co2[i] = 0;
} else {
co2[i] = co[da(i - p2n(x))] * co[da(i + p2n(x))];
}
}
For(i, 0, 2 * n - 1){
co[i] = co2[i];
}
return;
} else {
up0();
return;
}
}int main(){
cin >> n >> t;
For(i, 1, n){
int tev;
cin >> tev;
if (tev == 2){
tev = -1;
}
co[2 * i - 2] = tev;
}int tsk;
ll tox;
while (t != 0){
tsk = 0;
tox = 1;
while (tox <= t){
tox <<= 1;
tsk++;
}
tox >>= 1;
tsk--;
t -= tox;
up(tsk);
}
For(i, 0, 2 * n - 1){
if (co[i] == -1){
co[i] = 2;
}
cout << co[i] << ' ';
}
cout << endl;
return 0;}
/*
10 5
2 2 2 1 1 1 1 1 1 2
-1 0 -1 0 -1 0 1 0 1 0 1 0 1 0 1 0 1 0 -1 0
1 : 0 1 0 1 0 -1 0 1 0 1 0 1 0 1 0 1 0 -1 0 1
2 : 1 0 1 0 -1 0 -1 0 1 0 1 0 1 0 1 0 -1 0 -1 0
3 : 0 1 0 -1 0 1 0 -1 0 1 0 1 0 1 0 -1 0 1 0 -1
4 : -1 0 -1 0 -1 0 -1 0 -1 0 1 0 1 0 -1 0 -1 0 -1 0
5 : 0 1 0 1 0 1 0 1 0 -1 0 1 0 -1 0 1 0 1 0 1
*
*
* */
``` -
0
从网上摘抄的代码，但研究了半天不知道原理，但仍在此放出，希望各位帮忙解释一下原理。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 100100
using namespace std;
typedef long long ll;int n,tot;ll m;
char a[2][M],ans[M<<1];int main()
{
int x;
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&x),a[0][i]=x-1;
for(ll j=2;j<=m;j<<=1)
{
if(m & j)
{
++tot;
for(int i=1;i<=n;i++)
{
int x=(i+(j>>1)%n+n-1)%n+1;
int y=(i-(j>>1)%n+n-1)%n+1;
a[tot&1][i]=a[~tot&1][x]^a[~tot&1][y];
}
}
}
for(int i=1;i<=n;i++)
ans[i+i-1]=a[tot&1][i];
if(m & 1)
{
for(int i=1;i<=n;i++)
ans[i<<1]=ans[i+i-1]^ans[i==n?1:i<<1|1];
for(int i=1;i<=n;i++)
ans[i+i-1]=-1;
}
else
{
for(int i=1;i<=n;i++)
ans[i+i]=-1;
}
for(int i=1;i<=n<<1;i++)
printf("%d%c",ans[i]+1,i==n+n?'\n':' ');
} -
-1
醉了醉了！！ 打表+qword=AC ... ╮(╯▽╰)╭
测试数据 #0: Accepted, time = 0 ms, mem = 4324 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 4324 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 4324 KiB, score = 10
测试数据 #3: Accepted, time = 281 ms, mem = 4324 KiB, score = 10
测试数据 #4: Accepted, time = 437 ms, mem = 4324 KiB, score = 10
测试数据 #5: Accepted, time = 312 ms, mem = 4324 KiB, score = 10
测试数据 #6: Accepted, time = 281 ms, mem = 4324 KiB, score = 10
测试数据 #7: Accepted, time = 203 ms, mem = 4324 KiB, score = 10
测试数据 #8: Accepted, time = 234 ms, mem = 4324 KiB, score = 10
Accepted, time = 1778 ms, mem = 4324 KiB, score = 90pascal code
type int=longint; var k,i,j,t,n:int; m:qword; d,e,b:array[-100001..200001]of int; a:array[0..60]of qword=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768, 65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728, 268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368, 68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104, 8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656, 562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992, 18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744, 576460752303423488,1152921504606846976); begin readln(n,m); k:=-1; for i:=1 to n do begin read(d[i]); d[i-n]:=d[i]; d[i+n]:=d[i]; end; repeat inc(k); b[k]:=m mod 2; m:=m div 2; until m=0; for i:=k downto 1 do if b[i]=1 then begin t:=a[i-1] mod n; for j:=1 to n do if d[j-t]=d[j+t] then e[j]:=1 else e[j]:=2; for j:=1 to n do begin d[j]:=e[j]; d[j-n]:=e[j]; d[j+n]:=e[j]; end; end; if b[0]=1 then begin for i:=1 to n do if d[i]=d[i+1] then e[i]:=1 else e[i]:=2; for i:=1 to n do write(0,' ',e[i],' '); writeln; end else begin for i:=1 to n do write(d[i],' ',0,' '); writeln; end; end.我在秋名山等你**！！！**
-
-1
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int a[100005],n,t;
int b[200005];
int main (){
scanf("%d%d",&n,&t);
for (int i=0;i<n;i++)
scanf ("%d",&a[i]);for (int i=0,j=0;i<=2*n,j<=n;i+=2,j++)
b[i]=a[j];for (int i=0;i<2*n;i++)
cout<<b[i]<<' ';
cout<<'\n';for (int k=0;k<t-1;k++){
for (int i=1;i<2*n;i+=2){
if (b[i-1]==b[i+1] && b[i-1]!=0)
b[i]=1;
else
if (b[i-1]!=0 && b[i+1]!=0)
b[i]=2;b[i-1]=0;
}
for (int i=0;i<2*n;i++)
cout<<b[i]<<' ';
cout<<'\n';
}
for (int i=0;i<2*n;i++)
cout<<b[i]<<' ';
//while (1);
return 0;
}测试数据 #0: Accepted, time = 0 ms, mem = 1128 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1128 KiB, score = 10
测试数据 #2: Accepted, time = 12 ms, mem = 1128 KiB, score = 10
测试数据 #3: Accepted, time = 234 ms, mem = 1128 KiB, score = 10
测试数据 #4: Accepted, time = 280 ms, mem = 1128 KiB, score = 10
测试数据 #5: Accepted, time = 223 ms, mem = 1128 KiB, score = 10
测试数据 #6: Accepted, time = 245 ms, mem = 1128 KiB, score = 10
测试数据 #7: Accepted, time = 267 ms, mem = 1124 KiB, score = 10
测试数据 #8: Accepted, time = 208ms, mem = 1128 KiB, score = 10 -
-1
yzl609271536 LV 10 @ 2009-08-11 10:38:04
program yzl;
var
i,j,p,q:longint;
n,k,t:int64;
a,b:array [0..200001] of integer;
f:array [0..200001] of longint;
// power:array [0..100] of int64;
power,rol:int64;
g:array [0..2000001,0..1] of integer;
beginreadln(n,t);
for i:=1 to n do begin
read(a[2*i-1]);
if a[2*i-1]=2 then
a[2*i-1]:=-1;
g[2*i-1,1]:=a[2*i-1];
end;
n:=n shl 1;
rol:=0;
while t>0 do begin
power:=1;
while power shl 1 -
-2
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 25ms
├ 测试数据 05：答案正确... 134ms
├ 测试数据 06：答案正确... 25ms
├ 测试数据 07：答案正确... 56ms
├ 测试数据 08：答案正确... 9ms
├ 测试数据 09：答案正确... 72ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：321ms
curimit神牛太强了，澳淄 -
-3
program P1554; var te,temp2:array[0..100000] of boolean; bin:array[1..60] of boolean; t,k:qword; i,j,n,temp,temp1:longint; begin readln(n,t); for i:=1 to n do begin read(temp); if temp=2 then te[i]:=true else te[i]:=false; end; te[0]:=te[n]; temp:=0; while t<>0 do begin inc(temp); if t mod 2=1 then bin[temp]:=true else bin[temp]:=false; t:=t div 2; end; k:=1; for i:=1 to temp-1 do k:=k*2; for i:=temp downto 2 do begin k:=k div 2; if bin[i] then begin temp1:=k mod n; for j:=0 to n-1 do temp2[j]:=te[(j-temp1+n) mod n] xor te[(j+temp1) mod n]; te:=temp2; end; end; te[n]:=te[0]; if bin[1] then begin for i:=1 to n-1 do begin write('0 '); if (te[i] xor te[i+1]) then write('2 ') else write('1 '); end; write('0 '); if (te[n] xor te[1]) then write('2 ') else write('1 '); end else for i:=1 to n do begin if te[i] then write('2 ') else write('1 '); write('0 ') end; end.
lxy8584099
LV 7
@ 2018-08-22 17:17:12
