hdu_5683_zxa and xor(非正解的暴力)

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=5683

题意:

问题描述
zxa最近对按位异或(exclusive disjunction)产生了极大的兴趣,为此他拿出了一个长度为nn的非负整数序列a_1,a_2,\cdots,a_na​1​​,a​2​​,⋯,a​n​​。

zxa觉得这样太单调了,于是他定义了一种方法funct(x,y)funct(x,y),表示将a_xa​x​​不可逆转地修改为yy后计算\otimes_{1\leq i < j\leq n}{(a_i+a_j)}⊗​1≤i<j≤n​​(a​i​​+a​j​​)作为该方法的返回值。

zxa很好奇,如果他对这个序列调用mm次这样的方法,那么每次得到的返回值分别是多少,你能帮助他吗?

提示:\otimes_{1\leq i < j\leq n}{(a_i+a_j)}⊗​1≤i<j≤n​​(a​i​​+a​j​​)即(a_1+a_2)\otimes(a_1+a_3)\otimes\cdots\otimes(a_1+a_n)\otimes(a_2+a_3)\otimes(a_2+a_4)\otimes\cdots\otimes(a_2+a_n)\otimes\cdots\otimes(a_{n-1}+a_n)(a​1​​+a​2​​)⊗(a​1​​+a​3​​)⊗⋯⊗(a​1​​+a​n​​)⊗(a​2​​+a​3​​)⊗(a​2​​+a​4​​)⊗⋯⊗(a​2​​+a​n​​)⊗⋯⊗(a​n−1​​+a​n​​)。
输入描述
第一行有一个正整数TT,表示有TT组数据。

对于每组数据:

第一行有两个正整数nn和mm。

第二行有nn个非负整数,表示a_1,a_2,\cdots,a_na​1​​,a​2​​,⋯,a​n​​。

接下来mm行,第i(1\leq i\leq m)i(1≤i≤m)行有两个非负整数xx和yy,表示第ii调用的是funct(x,y)funct(x,y)。

每一行相邻数字之间只有一个空格。

1\leq T\leq 1000,2\leq n\leq 2\cdot10^4,1\leq m\leq 2\cdot10^4,0\leq a_i,y\leq 10^9,1\leq x\leq n,1\leq\sum{n},\sum{m}\leq10^51≤T≤1000,2≤n≤2⋅10​4​​,1≤m≤2⋅10​4​​,0≤a​i​​,y≤10​9​​,1≤x≤n,1≤∑n,∑m≤10​5​​
输出描述
对于每组数据,输出mm行,第i(1\leq i\leq m)i(1≤i≤m)行包含一个非负整数,表示第ii次调用方法的返回值。
输入样例
1
3 3
1 2 3
1 4
2 5
3 6
输出样例
4
6
8
Hint
第一次操作后序列为\{4,2,3\}{4,2,3},(4+2)\otimes(4+3)\otimes(2+3)=4(4+2)⊗(4+3)⊗(2+3)=4。

第二次操作后序列为\{4,5,3\}{4,5,3},(4+5)\otimes(4+3)\otimes(5+3)=6(4+5)⊗(4+3)⊗(5+3)=6。

第三次操作后序列为\{4,5,6\}{4,5,6},(4+5)\otimes(4+6)\otimes(5+6)=8(4+5)⊗(4+6)⊗(5+6)=8。

题解:在BC的终测 我居然TLE了,不科学,唐老师放宽了时限,和我写法差不多,常数也差不多的都过了,然而我没过,很是不爽,然而在OJ上提交 5600+ms A C

 #include<cstdio>
#define FFC(i,a,b) for(int i=a;i<=b;i++)
int s[],da[];
int main(){
int t,m,n,a,b;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
FFC(i,,n)scanf("%d",&s[i]);
FFC(i,,n){
int ans=;
FFC(j,i+,n)ans=ans^(s[i]+s[j]);
da[i]=ans;
}
FFC(i,,m){
scanf("%d%d",&a,&b);
int tmp=s[a];
s[a]=b;
int ans=,aans=;
FFC(j,a+,n)ans=ans^(b+s[j]);
da[a]=ans;
FFC(j,,a-)da[j]=da[j]^(s[j]+tmp),da[j]=da[j]^(s[j]+b);
FFC(i,,n)aans^=da[i];
printf("%d\n",aans);
}
}
return ;
}
上一篇:【iCore3 双核心板】例程十二:通用定时器实验——定时点亮LED


下一篇:selenium webdriver读取excel进行数据驱动测试