A. Square Counting
给你一个序列 ，每一个元素满足两个条件：
已知 和序列之和 ，求对于任意 ， 的个数。
组数据。
可以证明结果唯一。
结论：
题目中，首先看到了 结果唯一。所以证明的起点就在这里。
因为 范围内的数至多有 个，最小总值为 ，最大总值为 ，所以数列中的 不能被 范围内的数代替，因此答案唯一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
long long n,s;
cin>>n>>s;
cout<<(s/(n*n))<<endl;
}
return 0;
}
|
B. Quality vs Quantity
涂色问题。有一个序列 ，可以有三种状态：标记为红色，标记为蓝色，不标记颜色。
设标记红色的元素集合为 ，绿色为 。
那么，是否能够满足
且 ？
能输出 YES，不能输出 NO。（虽然输出 yEs 和 YeS 是一样的）
贪心。想要 和大于 和，而且 数量还得更少，那么只能让 中的元素远远大于 中元素。
那么排一遍升序，从左到右选，左边选 个数当做 ，右边选择 个数当做 ，如果扫完全序列都不能满足，那必然是 nO 了。
单次 ，均摊总时间复杂度 。
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
| #include<bits/stdc++.h>
using namespace std;
long long a[1000001];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
long long s1=a[1]+a[2],s2=a[n];
int i=2,j=n;
bool flag=0;
while(i+1<j)
{
if(s1<s2) {flag=1;break;}
i++;j--;
s1+=a[i];s2+=a[j];
}
if(s1<s2) flag=1;
if(flag) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
|
C. Factorials and Powers of Two
称一个数为强数，当且仅当这个数为 或 ，其中 。（ 为非负整数集合）
求一个数最最少可以被分解为多个强数之和？
如果不可以被分解，那么输出 。
首先， 是不可能的。因为任意一个非负整数都可以转换成对应的二进制。而对应二进制位上的 ，单独拿出来，就都是强数。
比如 。
那么，现在就想，如何使 （即分解个数）最小了。
若直接枚举强数相加，那么时间复杂度为 。比较危险。
但是，发现只要确定阶乘的强数，反过来就可以推出二次幂的强数个数。
所以，可以只枚举 次就可以了。
（ 来自何方？ 的逆阶乘小于等于 。）
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
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<bits/stdc++.h>
using namespace std;
int minx=-1;
long long a[17];
long long fac(int x)
{
long long ans=1;
for(int i=1;i<=x;i++) ans*=i;
return ans;
}
void init()
{
for(int i=1;i<=16;i++) a[i]=fac(i);
}
int bitcount(long long x)
{
int ans=0;
do
ans+=(x&1);
while(x>>=1);
return ans;
}
void dfs(int now,int tot,long long sum)
{
if(now==16+1||sum-a[now]<0)
{
minx=min(minx,tot+bitcount(sum));
return;
}
dfs(now+1,tot+1,sum-a[now]);
dfs(now+1,tot,sum);
}
int main()
{
init();
int t;
cin>>t;
while(t--)
{
long long n;
int ans=0;
minx=1e9;
cin>>n;
dfs(1,0,n);
cout<<minx<<endl;
}
return 0;
}
|