CodeForce刷题表
Day2
题意:
数组进行k次操作，询问第x个位置上的数是多少。
每次操作重置数组，新的a[i]等于a[i]在该数组中出现的次数
如: 2 1 1 4 3 1 2 ==> 2 3 3 1 1 3 2 ==> ……
思路：
可以发现数组其实是逐渐趋于统一的，相同的数一直都是相同的，不相同的数可能会变为相同的，当所有的数字都等于该数字出现的次数时，之后不再改变。
这样的话，最多操作n次(不是一个精确的值，实际上应该少于n)就会让他不再改变，对最多2000个数操作2000次，1e6时间复杂度是过得去的。
但是询问次数q = 1e5，如果每次询问都重新跑一遍，大概率要超时！所以就做一个预处理，询问时直接输出。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
int a[2005][2005];
int main(){
int t;
cin>>t;
while(t--) {
int n,q,x,k,real;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[0][i];
for(int i=1;i<=n;i++) {
int w[2005] = {0};
for(int j=1;j<=n;j++)
w[a[i-1][j]]++;
for(int j=1;j<=n;j++)
a[i][j]=w[a[i-1][j]];
}
cin>>q;
while(q--) {
cin>>x>>k;
cout<<a[min(k,n)][x]<<endl;
}
}
return 0;
}
|
总结：
有询问的题目要考虑询问时会不会超时，如果超时可能要考虑做一个预处理，操作完询问的题大概率要做预处理把。
题意：
选择一个k，每次选择k个数，得到一个x = ai1 & ai2 & … & aik ，然后使所选的数都减去x，如果最后能使每一个数都等于0，就输出这个k，问满足条件的数都有哪些
思路：
(因为&操作后只剩下这k个数在二进制下都为1的位置，所以相当于把他们同为1的地方给删掉，也就是二进制的该位置上每次可以减去k个数，因此二进制下k必须是该位置的因子才可以完全去掉)
枚举二进制前30位(int范围内)，记录该位置上有多少个1，如果没有1，那么任何数都不会对他产生影响，所有的计数器都+1；如果有1，那么把他的因子都+1。
结束之后如果某个数字的计数器==31 (任何数%1 == 0，所以a[1]实际上就是31)，即他是每一个数的因子，那么他就可以做到把所有位置都变成0，因此输出这个数。
例如： 4 4 4 4 =>二进制 0100 0100 0100 0100 => 0 4 0 0 ,如果选一个数那么每次可以去掉0 1 0 0，选两个数每次可以去掉0 2 0 0，选三个数每次可以去掉0 3 0 0，选四个数每次可以去掉0 4 0 0，显然只有1 2 4满足题目要求。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
int a[N],cnt[N];
int main(){
int t;
cin>>t;
while(t--) {
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],cnt[i]=0;
for(int i=0;i<=30;i++) {
int t = 0;
for(int j=1;j<=n;j++)
if((1<<i)&a[j])
t++;
if(cnt==0)
for(int j=1;j<=n;j++)
cnt[j]++;
else
for(int j=1;j<=t;j++)
if(t%j==0)
cnt[j]++;
}
for(int i=1;i<=n;i++)
if(cnt[i] == cnt[1])
cout<<i<<" ";
cout<<endl;
}
return 0;
}
|
总结：
位运算的题最好是按照二进制的思想来解决，把每一个数都看作是二进制，这样比直接看作十进制简单不少！
题意：
有n个人，把n个人分成2组，要求每组在周一到周五任意一天全都有空(全是1)，并且2组所选的日期不同。
思路：
假设一组是某一天A，然后另一组是另一天B。如果选定的一天A有空的不足一半，直接pass掉，如果超过了，那么就记录第A天和第B天都有空 以及 第A天没空第B天有空的。可以知道，最多有A有空的人-人数的一半或者是两天都有空的人(其中较小的一个)，这些人就是可以为B提供贡献的，如果这个值 加上 第A天没空第B天有空的大于人数的一半，那么这存在，如果没有出现这样的情况，就是不存在。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
int a[1005][10];
int main(){
int t;
cin>>t;
while(t--) {
int n,f=1;
int q[10] = {0};
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=5;j++) {
cin>>a[i][j];
if(a[i][j])
q[j]++;
}
for(int i=1;i<=5&&f;i++) {
if(q[i]<n/2)
continue;
int last = q[i] - n/2;
for(int j=i+1;j<=5&&f;j++) {
int same=0,diff=0;
for(int k=1;k<=n&&f;k++) {
if(a[k][i] && a[k][j])
same++;
else if(!a[k][i] && a[k][j])
diff++;
int tmp = min(same,last);
if(tmp + diff >= n/2)
f = 0;
}
}
}
if(f)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
return 0;
}
|
总结：
这也算半个数学题了吧，一定要动笔比划一下，不然真的好绕啊，想明白数值的关系其实就是一个暴力枚举。
微信
支付宝