Question

三道C/C++题，急求帮助，能给几题是几题，要快！

选举(election)
问题描述：
美国的选举制度是比较有趣的，投票者被分成k个组，如果超过半数的组投赞成票，决议就可以通过；每组是投赞成票还是反对票也由每组内部投票决定，若这一组有超过半数的人投赞成票，那么这一组就投赞成票。现在我们来模拟一下，已经组数和每组的，编程计算要使得决议通过至少需要多少人投赞成票。
输入格式：
第一行为正整数t(≤50)，表示数据组数；每组数据中，第一行为正整数k(≤1000)，第二行为以空格隔开的k个正整数ai(≤1000)，表示每组人数。数据保证k和ai都是奇数。
输出格式：
对于每组数据，输出相应的结果。
输入样例
2
3
5 7 5
7
25 5 7 9 31 59 13

输出样例
6
19

破损的数字(digit)
问题描述：
一天，Charley在纸上写了一个数字，它可以被77整除。后来这个数字中，有四个连续的数码被墨水污染了，看不清楚。请你帮你找出这四个数字可能的最大值。
输入格式：
第一行为正整数t(≤5)，表示数据组数；接下来t行，每行一个整数，其中有4个连续的xxxx表示被污染的数字N(10^5≤N≤10^1000000)。
数据规模：
30%的数据中，N≤10^15；100%的数据中，N≤10^1000000。
输出格式：
对于每组数据，输出最大可能的77的倍数。
输入样例
2
1xxxx
1234567xxxx7654321

输入样例
19943
123456799337654321

平方和分解(squares)
问题描述：
John喜欢研究数字，他把一些连续整数的平方和累加起来，例如：21^2+22^2+23^2+24^2=2030，然后他又发现：25^2+26^2+27^2=2030。现在他把这个问题反过来看，给定一个正整数n，能否把n分解成若干个连续的正整数的平方和。John发现有时数字太大，他无法验证，请你编程帮助他验证这个分解式。
输入格式：
仅一个正整数n(≤10^14)。
输出格式：
第一行是分解方案数t；接下来t行，每行表示一个解，每个解只要输出连续的第一个数a和最后一个数b。按a值大小的升序输出。如果不能分解，直接输出1个0。
输入样例
2030

输入样例
2
21 24
25 27

Answer 1

election
#include <cstdio>
#include <cstdlib>
int cmp(const void *p, const void *q){
return *(int *)p - *(int *)q;
}
int main(){
freopen("election.in", "r", stdin);
freopen("election.out", "w", stdout);
int t, k, a[1010];
scanf("%d", &t);
while (t--){
scanf("%d", &k);
for (int i=0; i<k; i++)
scanf("%d", &a[i]);
qsort(a, k, sizeof(int), cmp);
int ans=0;
for (int i=0; i<=k/2; i++)
ans+=a[i]/2+1;
printf("%d\n", ans);
}
return 0;
}

digit

#include <stdio.h>
#include <string.h>
const int M=1000001;
char s[M];
int main(){
freopen("digit.in","r",stdin);
freopen("digit.out","w",stdout);
int t;
scanf("%d", &t);
while (t--){
scanf("%s", s);
int ans1=0, len=strlen(s), pos;
for (int i=0; i<len; i++){
if (s[i]=='x') {
s[i]='9';
pos=i;
}//求最后一个x的位置:pos
ans1=(ans1*10+s[i]-'0')%77;
}

//先求xxxx全填9999时s除以77的余数:ans1

if (ans1==0){ /*
for (int i=0; i<=pos-4; i++)
printf("%c", s[i]);
printf("9999");
for (int i=pos+1; i<len; i++)
printf("%c", s[i]);
printf("\n");*/
puts(s);
continue;
}//如果全填9999恰好能整除，直接输出

int ans2=1, ten=10, tpos=len-pos-1;
while (tpos>0){
if (tpos%2) ans2=ans2 * ten %77;
tpos/=2; ten=ten*ten%77;
}//再求10的tpos次方对77的余数: ans2，算法：快速幂

int k=1, ans3=ans2;
while (ans3!=ans1){
k++;
ans3=ans2*k%77;
}//再求k*ans2 % 77的余数等于 ans1 的第一个k值

for (int i=0; i<=pos-4; i++)
printf("%c", s[i]);
printf("%d", 9999-k);
for (int i=pos+1; i<len; i++)
printf("%c", s[i]);
printf("\n");
}
return 0;
}
/*
1xxxx987
19999987 : ans1 =5
1000 : ans2 =1
5000 5
19994987
*/

squares
#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
int a[10][2];
int main(){
freopen("squares.in","r",stdin);
freopen("squares.out","w",stdout);
ll n, s, fm, to;
cin>>n;
/*fm=1ll; to=(long long)(pow((24.0)*n, 1.0/3)/2-1);
s=to*(to+1)*(to*2+1)/6; //纯数学方法直接计算出to
*/
fm=1ll; s=fm*fm; to=fm;
int ns=(int)(sqrt(1.0*n)), ans=0;
while (to<=ns){
if (s<n){
to++; s+=to*to;
}//队尾入列
else if (s>n){
s-=fm*fm; fm++;
}//队首出列
else {
a[ans][0]=(int)(fm); a[ans][1]=(int)(to);
ans++; to++; s+=to*to;
}
}
printf("%d\n", ans);
for (int i=0; i<ans; i++){
printf("%d %d\n", a[i][0],a[i][1]);
}
return 0;
}

Answer 2

第一题：
#include <stdio.h>
int digi[1010];
int main()
{
int n,m,te,tt;
int i,k;
int s,s2;
scanf("%d",&n);
while(n--){
scanf("%d",&m);
tt=m/2;
s=0;
for(i=0;i<m;i++){
scanf("%d",&te);
if(!s) {
digi[s]=te;s++;continue;
}
for(k=s-1;k>=0;k--){
if(te>=digi[k]) {
digi[k+1]=te;s++;break;
}
digi[k+1]=digi[k];
}
if(k<0){
digi[0]=te;s++;
}
}
s2=0;
for(k=0;k<=tt;k++){
//printf("%d ",digi[k]);
s2+=(digi[k]/2+1);
}
//printf("\n");
printf("%d\n",s2);
}
return 0;
}

追问

谢谢啦，后面两题有吗？？

追答