2020年春混合个人训练第三十场
感觉题都很好就是我不会qwq
问题 A: 选举
题目描述
C国的总统选举委员会最近遇到了一些麻烦。他们在统计各省对H先生的支持率（百分比）时，把支持率四舍五入到了整数。等他们公布结果后，该国媒体发现这些省份的支持率之和不等于100（百分比）！在媒体黑幕声的质疑下，他们不得不找你寻求帮助。
你将得到各省四舍五入后的支持率，请计算这些省份的支持率在四舍五入前的和是否可能等于100？支持率是以百分比的形式统计的。
请注意，各省的支持率可以是一个包含任意多位的有限小数。一个小数在四舍五入到整数时，若小数点后第一位小于5则舍，大于等于5则入。
例如：
26、17、58是一种可能的支持率，因为它们可能是25.8、16.5、57.7四舍五入后得到的，而25.8+16.5+57.7=100。
49、49是一种不可能的支持率，因为当9的个数有限时，无论有多少个9，均有49.499…99+49.499…99<100。
输入
输入包含多组数据，第一行是一个整数T，表示数据组数。
接下来是T组数据，每组数据的第一行是一个整数N，表示参与选举的省份个数。第二行是N个整数，表示各省四舍五入后的支持率。
输出
对于每组数据，若是一种可能的支持率，输出Yes，否则输出No。
样例输入 Copy
2 2 49 49 3 26 17 58
样例输出 Copy
No Yes
提示
对于30%的数据，1<=n<=3；
对于50%的数据，1<=n<=5；
对于80%的数据，1<=四舍五入后各省的支持率<=99；
对于100%的数据，1<=n<=10000，输入数据中的所有整数均在有符号16位整数范围内。
思路：
考虑极限情况，从而得到支持率可能的范围是否包含100。对于一个数x来说，四舍五入前的可能范围是【x-0.5,x+0.5），要注意边界。
本题可能会有非法数据，比如-1和101，这时候直接特判输出No即可。
代码：
const int maxn=2e5+100;
double a[maxn];
int n;
int main(){
int T=read();
while(T--){
n=read();
double sum=0;
bool flag=1;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]<0||a[i]>100) flag=0;
sum+=a[i];
}
if(!flag) puts("No");
else{
double eps=100.0;
if(sum-0.5*n<=eps&&sum+0.5*n>eps) puts("Yes");
else puts("No");
}
}
return 0;
} 问题 C: 序列变换
题目描述
给定一个长度为N的数列Ai。
你可以对数列进行若干次操作，每次操作可以从数列中任选一个数，把它移动到数列的开头或者结尾。
求最少经过多少次操作，可以把数列变成单调不减的。“单调不减”意味着数列中的任意一个数都不大于排在它后边的数。
输入
第一行是一个正整数N。
第二行是N个正整数Ai。
输出
输出一个整数，表示最少需要的操作次数。
样例输入 Copy
5 6 3 7 8 6
样例输出 Copy
2
提示
对于30%的数据，满足1≤n≤10。
对于60% 的数据，满足1≤n≤1000。
对于100% 的数据，满足1≤n≤1000000，1≤Ai≤1000000
思路：
问题 D: 约会时间
题目描述
从前，小兔发现了一个神秘的花园。
花园是一个 n 行 m 列的矩阵，第 i 行 j 列的花的美丽度为 ai,j，一个合法的约会场所为任意一个正方形子矩阵，定义子矩阵的浪漫度为这个子矩阵的两条对角线上的花的美丽度之和。
现在小兔想选一个面积大等于 1 的约会场所使得场所的浪漫度最大，以便和小鹿约会，因为小兔忙着 AKIOI ，所以她把这个问题交给了你。
输入
第一行，两个正整数 n,m。
接下来是一个 n 行 m 列的矩阵，表示各个位置上花的美丽度。
输出
仅一行，一个正整数，表示最大的浪漫度。
样例输入 Copy
3 3 2 -1 3 -4 2 1 1 2 -1
样例输出 Copy
7
提示
对于 40%的数据，n,m≤10。
对于 100%的数据，1≤n,m≤300,∣ai∣≤104。
思路：
问题 E: 异或和
题目描述
有一个 n 个元素的数组 a ，设f(i,j)=ai xor aj。
现在你要求对于所有的 1≤i≤j≤n 的 f(i,j)之和。
输入
第一行，一个正整数 n 。
接下来 n 个数，表示 ai。
输出
仅一行，一个正整数，表示总和。
样例输入 Copy
3 1 2 3
样例输出 Copy
6
提示
对于 30% 的数据，n≤3000。
另外 20% 的数据，ai≤1。
对于 100% 的数据，1≤n≤2×105,0≤ai≤105。
思路：
一般异或的题目都考虑按位求贡献，所以我们可以对每个数进行二进制拆分，按位求贡献后计算总和。
异或的一个性质是a^a=0,又因为二进制拆分后每一位的可能性只有0和1，假设本位拆开后是n个0，m个1，那么任选两个结合后的总异或和一定是n*m，因为只有0^1是有意义的。对总体的贡献就是再乘1<<i；
要注意二进制拆分的时候，前导零是无法统计进去的，但是计算的时候由必须用到0的个数，所以这里要处理一下。
感觉跟每日一题有点像。
代码：
const int maxn=2e5+100;
ll n,a[maxn];
ll dp[maxn][2];
///dp[i][1]表示第i位1的数量
///dp[i][0]表示第i位0的数量
void cul(ll x){
ll tot=0,cnt=66;
while(cnt--){
dp[tot++][x&1]++;
x/=2;
}
}
void AC(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
cul(a[i]);
}
ll res=0;
for(int i=0;i<63;i++){
/// cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
res+=(1<<i)*dp[i][1]*dp[i][0];
}
printf("%lld\n",res);
}
问题 G: 数学课
题目描述
求 ax+b=0 的解。
输入
共有三组数据。
三行，每行两个整数，a,b。
输出
共有三组数据。
若有一个实数解，输出 x= 你求出的解，四舍五入保留 3 位小数，正负号要保留。
若无实数解，输出 No Solution。
若有无限组解，输出 Infinite Solutions。
样例输入 Copy
1 -1 4 -3 7 16
样例输出 Copy
x=1.000 x=0.750 x=-2.286
提示
对于 100% 的数据，∣a∣,∣b∣≤109。
思路：
签到题没啥好说的，注意特判一下就好。
四舍五入的话，printf自带四舍五入。
代码：
ll a,b;
int main(){
while(cin>>a>>b){
if(a==0&&b==0) cout<<"Infinite Solutions"<<endl;
else if(b==0){
cout<<"x=0.000\n";
}
else if(a==0) cout<<"No Solution"<<endl;
else{
cout<<"x=";
if(a*b>0) cout<<"-";
printf("%.3f\n",1.0*abs(b)/abs(a));
}
}
return 0;
} 
京公网安备 11010502036488号