华东交通大学2017年ACM双基程序设计大赛题解
簡單題
Time Limit : 3000/1000ms (Java/Other)???Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 19???Accepted Submission(s) : 14
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
大吉大利今晚吃雞
Time Limit : 3000/1000ms (Java/Other)???Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 1379???Accepted Submission(s) : 501
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
最近流行吃雞,那就直接輸出一行"Winner winner ,chicken dinner!"(沒有雙引號)
模板代碼：
#include <stdio.h>
int main(){
printf("hello world\n");
return 0;
}
Input
沒有輸入
Output
輸出一行"Winner winner ,chicken dinner!"注意要換行
Sample Output
Winner winner ,chicken dinner!
解題報告：
簽到題
#include <stdio.h>
int main(){
printf("Winner winner ,chicken dinner!\n");
return 0;
}
?
1002??????
跳舞
Time Limit : 3000/1500ms (Java/Other)???Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 354???Accepted Submission(s) : 38
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
一天YZW參加了學(xué)校組織交際舞活動，活動的開始活動方分別給男生和女生從1-n進行編號，按照從小到大順時針的方式進行男女搭檔分配，相同編號的男女組合成一對，例如一號男生與一號女生配對，以此類推。可是YZW對其中一個小姐姐一見鐘情，于是機智的他向管理員提出了兩種操作
1.在這種情況下，管理員會給出移動的方向和大小，然后所有的男生向著這個方向移動x個位置。2.管理員會把相鄰的奇數(shù)和偶數(shù)位置上的男生互換。
在其中女生的位置是不會變的。可是YZW不知道經(jīng)過這些Q次操作后，他自己身在何方，能否到達自己喜歡的小姐姐身邊。
Input
輸入一個T代表T組數(shù)據(jù)(T<=10)，每組輸入一個n和q(2≤n≤200000,1≤q≤1000000,其中n為偶數(shù)),分別代表有n對男女和有q次操作。
接下來是q行，每一行輸入：
1.x代表所有男生移動的位置的大小。同時x>0表示順時針移動，x<0表示逆時針移動。
2.代表管理員會把相鄰的奇數(shù)和偶數(shù)位置上的男生互換。
Output
輸出1號到n號小姐姐配對的分別是幾號男生。
Sample Input
1
6 3
1 2
2
1 2
Sample Output
4 3 6 5 2 1
?
解題報告：記錄第一個和第二個男生的位置n1和n2，將所有的操作的影響加在這個兩位置上，其中第一種操作相當(dāng)于n1和n2加上或者減去x,第二種操作相當(dāng)于奇數(shù)位置上的數(shù)+1,偶數(shù)位上的數(shù)-1.然后通過這樣兩個位置推導(dǎo)出所有的其他的位置即可
代碼：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<bitset>
#include<set>
#include<map>
using namespace std;
#define LL long long
#define pi (4*atan(1.0))
#define eps 1e-8
#define bug(x)? cout<<"bug"<<x<<endl;
const int N=1e6+10,M=7e6+10,inf=1e9+10,MOD=10;
const LL INF=1e18+10;
?
int a[N];
int main()
{
??? int T;
??? scanf("%d",&T);
??? while(T--)
??? {
??????? int n,q;
??????? scanf("%d%d",&n,&q);
??????? int s=1,e=2;
??????? while(q--)
??????? {
??????????? int t;
??????????? scanf("%d",&t);
??????????? if(t==1)
??????????? {
??????????????? LL x;
??????????????? scanf("%lld",&x);
??????????????? x%=n;
??????????????? s+=x;
?? ?????????????e+=x;
??????????????? if(s>n)s-=n;
??????????????? if(s<=0)s+=n;
??????????????? if(e>n)e-=n;
??????????????? if(e<=0)e+=n;
??????????? }
??????????? else
??????????? {
??????????????? if(s%2)s++;
??????????????? else s--;
??????????????? if(e%2)e++;
??????????????? else e--;
??????????? }
??????? }
??????? for(int i=1;i<=n/2;i++)
??????? {
??????????? a[s]=i*2-1;
??????????? a[e]=i*2;
??????????? s+=2;
??????????? e+=2;
??????????? if(s>n)s-=n;
??????????? if(e>n)e-=n;
??????? }
??????? for(int i=1;i<=n;i++)
??????????? printf("%d%c",a[i],(i==n?'\n':' '));
??? }
??? return 0;
}
1003
這是道水題
Time Limit : 3000/1000ms (Java/Other)???Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 827???Accepted Submission(s) : 179
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
有兩個球在長度為L的直線跑道上運動，兩端為墻。0時刻小球a以1m/s的速度從起點向終點運動，t時刻小球b以相同的速度從終點向起點運動。問T時刻兩球的距離。這里小球與小球、小球與墻的碰撞均為彈性碰撞，所有過程沒有能量損失。
Input
先輸入一個q，代表q組數(shù)據(jù)，然后每組3個整數(shù) L，t，T。
1<=L<=1000;0<=t<=1000;t<=T<=1000;
Output
一個整數(shù)，代表答案。
Sample Input
2
10 4 7
8 3 9
Sample Output
0
5
解題報告：單獨考慮每個小球，分別求出最后小球的位置pos1，pos2。答案即為abs(pos1-pos2)。
代碼:
#include?<iostream>
#include?<cstdio>
#include?<cmath>
using?namespace?std;
int?main()
{
????int?L,t,T;
????int?cas;
????scanf("%d",&cas);
????while(cas--&&scanf("%d?%d?%d",&L,&t,&T)){
????????int?n=T%(2*L);
????????int?l;
????????if(n>=L){
????????????l=L-(n-L);
????????}else{
????????????l=n;
????????}
????????int?r;
????????int?n2=(T-t)%(2*L);
????????if(n2>=L){
????????????r=L-(n2-L);
????????}else{
????????????r=n2;
????????}
????????r=L-r;
????????int?ans=r-l;
????????if(ans>=0){
????????????printf("%d\n",ans);
????????}else{
????????????printf("%d\n",-1*ans);
????????}
????}
????return?0;
}
?
1004
?
小廖的美麗子串
Time Limit : 3000/1000ms (Java/Other)???Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 7???Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
小廖最近沉迷于字符串，發(fā)現(xiàn)了一個問題，不能解決，非常懊惱。你能幫助他嗎？
對于一個長度為n的字符串，可以從大小為m的字母表里選取構(gòu)成。
定義一個字符串是美麗的就滿足：如果它的所有字符適當(dāng)改變順序后能夠組成一個回文串并且長度為奇數(shù)。
那么問題來了，大小為m的字母表組成的所有大小為n的串有m^n個，其包含美麗的子串的總和是多少？
Input
首先輸入一個t，代表t組數(shù)據(jù)t<=100
每組數(shù)據(jù)輸入n，m，n代表字符串的長度，m代表字母表的大小。
1<=n,m<=2000
Output
輸出結(jié)果mod1000000007。（mod表示取余）
Sample Input
3
2 2
3 2
10 3
Sample Output
8
32
1490526
解題報告：
設(shè)dp[i][j]表示長度為i的串有j種字符出現(xiàn)奇數(shù)次的個數(shù)。
dp[i][j]只能由dp[i-1][j-1]和dp[i-1][j+1]轉(zhuǎn)化來。
假如長度為i-1的串有j-1種字符出現(xiàn)奇數(shù)次，可以在剩余的（m-j+1）種字符選取一個；
假如長度為i-1的串有j+1種字符出現(xiàn)奇數(shù)次，可以在（j+1）種字符里任選一個；
所以狀態(tài)轉(zhuǎn)移方程為： dp[i][j]=(dp[i-1][j-1]*(m-j+1)+dp[i-1][j+1]*(j+1))
注意若能組成回文串，當(dāng)長度為奇數(shù)時j=1，否則j=0.
枚舉奇數(shù)長度i的串，其位置可以有（n-i+1）種，其它n-i位任意補齊，所以對于長度為i有
dp[i][1]*p[n-i]*（n-i+1）個，p[n-i]表示m的n-i次方。累加求和得到
ans=(ans+dp[i][i&1]*po[n-i]%mod*(n-i+1)%mod)%mod;
代碼：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<bitset>
#include<set>
#include<map>
#include<time.h>
#define?F(x)?(3*x*x-x)/2
using?namespace?std;
typedef?long?long?ll;
const?int?maxn=2000+10;
const?int?mod=1e9+7;
int?n,m;
ll?dp[maxn][maxn],po[maxn];
int?main()
{
????int?t;
????scanf("%d",&t);
????while(t--)
????{
????????scanf("%d%d",&n,&m);
????????dp[0][0]=1;dp[0][1]=0;
????????for(int?i=1;i<=n;i++)
????????{
????????????dp[i][0]=dp[i-1][1];
????????????dp[i][i]=(dp[i-1][i-1]*(m-i+1))%mod;
????????????int?j;
????????????if(i&1)j=1;
????????????else?j=2;
????????????for(;j<i;j+=2)
????????????{
????????????????dp[i][j]=(dp[i-1][j-1]*(m-j+1)+dp[i-1][j+1]*(j+1))%mod;
????????????}
????????}
????????po[0]=1;
????????for(int?i=1;i<=n;i++)
????????po[i]=(po[i-1]*m)%mod;
????????ll?ans=0;
????????for(int?i=1;i<=n;i++)
????????{
????????????????????if(i%2)
????????????ans=(ans+dp[i][i&1]*po[n-i]%mod*(n-i+1)%mod)%mod;
????????}
????????printf("%lld\n",ans);
????}
????return?0;
}
?
1005??????
矩陣
Time Limit : 3000/1000ms (Java/Other)???Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 168???Accepted Submission(s) : 52
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
假設(shè)你有一個矩陣，有這樣的運算A^(n+1) = A^(n)*A (*代表矩陣乘法)
現(xiàn)在已知一個n*n矩陣A,S = A+A^2+A^3+...+A^k,輸出S，因為每一個元素太大了，輸出的每個元素模10
Input
先輸入一個T(T<=10)，每組一個n,k(1<=n<=30, k<=1000000)
Output
輸出一個矩陣,每個元素模10(行末尾沒有多余空格)
Sample Input
1
3 2
0 2 0
0 0 2
0 0 0
Sample Output
0 2 4
0 0 2
0 0 0
解題報告：
倍增，復(fù)雜度log(k)*n*n
代碼：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<bitset>
#include<set>
#include<map>
using namespace std;
#define LL long long
#define pi (4*atan(1.0))
#define eps 1e-8
#define bug(x)? cout<<"bug"<<x<<endl;
const int N=1e6+10,M=7e6+10,inf=1e9+10,MOD=10;
const LL INF=1e18+10;
int n;
struct Matrix
{
??? short a[31][31];
??? Matrix()
??? {
??????? memset(a,0,sizeof(a));
??? }
??? void init()
??? {
??????? for(int i=0;i<n;i++)
??????????? for(int j=0;j<n;j++)
??????????????? a[i][j]=(i==j);
??? }
??? Matrix operator + (const Matrix &B)const
??? {
??????? Matrix C;
??????? for(int i=0;i<n;i++)
??????????? for(int j=0;j<n;j++)
??????????????? C.a[i][j]=(a[i][j]+B.a[i][j])%MOD;
??????? return C;
??? }
??? Matrix operator * (const Matrix &B)const
??? {
??????? Matrix C;
??????? for(int i=0;i<n;i++)
??????????? for(int k=0;k<n;k++)
??????????????? for(int j=0;j<n;j++)
??????????????????? C.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j])%MOD;
??????? return C;
??? }
??? Matrix operator ^ (const int &t)const
??? {
??????? Matrix A=(*this),res;
??????? res.init();
??????? int p=t;
??????? while(p)
??????? {
??????????? if(p&1)res=res*A;
??????????? A=A*A;
??????????? p>>=1;
??????? }
??????? return res;
??? }
}a[100],base;
?
int main()
{
??? int T;
??? scanf("%d",&T);
??? while(T--)
??? {
??????? int k;
??????? scanf("%d%d",&n,&k);
??????? for(int i=0;i<n;i++)
??????? for(int j=0;j<n;j++)
??????? scanf("%d",&a[1].a[i][j]);
??????? base=a[1];
??????? for(int i=2;i<=20;i++)
??????? {
??????????? a[i]=a[i-1]+(a[i-1])*base;
??????????? base=base*base;
??????? }
??????? base=a[1];
??????? Matrix now,ans;
??????? now.init();
??????? for(int i=19;i>=0;i--)
??????? {
??????????? if((1<<i)&k)
??????????? {
??????????????? ans=ans+a[i+1]*now;
??????????????? now=now*(base^(1<<i));
??????????? }
??????? }
??????? for(int i=0;i<n;i++)
??????? {
??????????? for(int j=0;j<n;j++)
?????????????? ?printf("%d%c",ans.a[i][j],(j==n-1?'\n':' '));
??????? }
??? }
??? return 0;
}
1006??????
大廈
Time Limit : 4000/2000ms (Java/Other)???Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 41???Accepted Submission(s) : 2
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
給你一個n(1<=n<=1000)層樓的大廈，每一樓里面有m(1<=m<=1000)房間，
每個房間一定的金錢X(1<=x<=1000)，假設(shè)不同樓層的房間是互通的，相同樓層的房間是不互通的。也就是說每層只能取一個，現(xiàn)在給你一個撿錢的機會。撿錢的方式不同，會導(dǎo)致你得到的錢的不同，求可能撿到的錢的前k大的和
Input
輸入一個T，表示T組樣例；
每組數(shù)據(jù)第一行輸入n，m，k
接下來輸入n行，每行m個數(shù)，代表這個房間擁有的金錢
Output
輸出可能撿到的錢的前k大的和
Sample Input
1
3 4 5
1 2 3 4
5 6 7 8
1 2 3 4
Sample Output
75
解題報告：
假設(shè)任意兩層為集合A B(從大到小排序）對于B集合的元素B[i]，顯然它和A[1]組合值最大，
如果B[i]+A[j]是前K大值中的一個，那么B[i]+A[k](1<=k < j)必然也是前K大的，
所以B[i]+A[j]被選則B[i]+A[j-1]之前就被選了，
所以優(yōu)先隊列中只需維護Size(B)個元素，首先把A[1]+B[i]全部進隊，
每次從隊首拿出一個組合(i,j)(表示A[i]+B[j])，把A[i+1]+B[j]進隊，
直到拿出K個元素為止，即為這兩個集合合并的前K大
n層的話只要把每次得到的結(jié)果和其他層按照這樣處理就可以了
代碼：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<bitset>
#include<set>
#include<map>
using namespace std;
#define LL long long
#define pi (4*atan(1.0))
#define eps 1e-8
#define bug(x)? cout<<"bug"<<x<<endl;
const int N=1e3+10,M=7e6+10,inf=1e9+10,MOD=10;
const LL INF=1e18+10;
?
?
int a[N],k,n,m;
vector<int>v;
struct is
{
??? int x,pos;
??? is(){}
? ??is(int _x,int _pos):x(_x),pos(_pos){}
??? bool operator <(const is &c)const
??? {
??????? return x<c.x;
??? }
};
int cmp(int x,int y)
{
??? return x>y;
}
vector<int> update(vector<int>v)
{
??? vector<int>ans;
??? if(v.size()*m<=k)
??? {
??????? for(int i=0;i<v.size();i++)
??????? for(int j=1;j<=m;j++)
??????????? ans.push_back(v[i]+a[j]);
??????? sort(ans.begin(),ans.end(),cmp);
??? }
??? else
??? {
??????? priority_queue<is>q;
??????? for(int i=1;i<=m;i++)
??????? {
??????????? q.push(is(a[i]+v[0],0));
??????? }
??????? int tmp=k;
??????? while(tmp--)
??????? {
??????????? is x=q.top();
??????????? ans.push_back(x.x);
??????????? q.pop();
??????????? if(x.pos+1<v.size())
??????????? q.push(is(x.x-v[x.pos]+v[x.pos+1],x.pos+1));
??????? }
??? }
??? return ans;
}
int main()
{
??? int T;
??? scanf("%d",&T);
??? while(T--)
??? {
??????? scanf("%d%d%d",&n,&m,&k);
??????? v.clear();
??????? v.push_back(0);
??????? for(int i=1;i<=n;i++)
??????? {
??????????? for(int j=1;j<=m;j++)
??????????????? scanf("%d",&a[j]);
??????????? v=update(v);
??????? }
??????? LL ans=0;
??????? for(int i=0;i<k;i++)
??????????? ans+=v[i];
??????? printf("%lld\n",ans);
??? }
??? return 0;
}
1007??????
超級牛奶
Time Limit : 6000/3000ms (Java/Other)???Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 52???Accepted Submission(s) : 6
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
超市有 n 種牛奶，每種牛奶的濃度為 ai/1000 。
Alice 想合成出一種濃度為 k/1000 的超級牛奶，每種牛奶可以買任意杯，她最少需要買多少杯牛奶呢？
Input
多組輸入，每組數(shù)據(jù)第一行輸入 k、n ，第二行輸入 n 個數(shù)ai，表示 n 種牛奶的濃度。
0<=k<=1000 , 1<=n<=1000000, 0<=ai<=1000 。 所給數(shù)據(jù)都是整數(shù)。
Output
每組數(shù)據(jù)輸出一個數(shù)，表示最少要買多少杯牛奶。 如果無法合成濃度為 k/1000 的牛奶，就輸出 -1 。
Sample Input
50 2
100 25
Sample Output
3
解題報告：要注意到濃度絕不會超過1000/1000。
假設(shè)選取m杯牛奶，則 (a1+a2+......+am) / m = n，變換一下為(a1-n)+(a2-n)+......+(am-n) = 0。即要選 m杯牛奶，其濃度減 n之和為0。而濃度不超過1000，故(a1-n)+(a2-n)+....+(as-n)的和肯定在 -1000~1000之間，所以可以 bfs解，相當(dāng)于找一條濃度0 到濃度0 的路徑，邊長為(ai-n)，這樣到每個可能濃度點的距離一定是最近的。
代碼：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<bitset>
#include<set>
#include<map>
using namespace std;
#define LL long long
#define pi (4*atan(1.0))
#define eps 1e-8
#define bug(x)? cout<<"bug"<<x<<endl;
const int N=1e3+10,M=7e6+10,inf=1e9+10,MOD=10;
const LL INF=1e18+10;
?
vector<int>v[5];
int flag[N][2];
int dp[N][2];
int main()
{
??? int k,n;
??? while(~scanf("%d%d",&k,&n))
??? {
??????? v[0].clear();
??????? v[1].clear();
??????? memset(flag,0,sizeof(flag));
??????? memset(dp,-1,sizeof(dp));
??????? int fuck=0;
??????? for(int i=1;i<=n;i++)
??????? {
??????????? int x;
??????????? scanf("%d",&x);
??????????? if(x==k)fuck=1;
??????????? if(x<k&&!flag[k-x][0])v[0].push_back(k-x),flag[k-x][0]=1;
??????????? if(x>k&&!flag[x-k][1])v[1].push_back(x-k),flag[x-k][1]=1;
??????? }
??????? if(fuck)
??????? {
??????????? printf("1\n");
??????????? continue;
??????? }
??????? dp[0][0]=0;
??????? dp[0][1]=0;
??????? for(int kk=0;kk<=1;kk++)
??????? for(int i=0;i<v[kk].size();i++)
??????? {
??????????? for(int j=v[kk][i];j<=1000;j++)
??????????? {
??????????????? if(dp[j-v[kk][i]][kk]!=-1)
??????????????? {
??????????????????? if(dp[j][kk]==-1)dp[j][kk]=dp[j-v[kk][i]][kk]+1;
??????????????????? else dp[j][kk]=min(dp[j][kk],dp[j-v[kk][i]][kk]+1);
??????????????? }
??????????? }
??????? }
??????? int ans=inf;
??????? for(int i=1;i<=1000;i++)
??????? if(dp[i][0]!=-1&&dp[i][1]!=-1)
??????? {
??????????? ans=min(ans,dp[i][0]+dp[i][1]);
??????? }
??????? if(ans==inf)printf("-1\n");
??????? else printf("%d\n",ans);
??? }
??? return 0;
}
?
1008??????
子序列
Time Limit : 3000/1000ms (Java/Other)???Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 499???Accepted Submission(s) : 270
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
長度為 n 的序列，把它劃分成兩段非空的子序列，定義權(quán)值為：兩段子序列的最大值的差的絕對值。求可能的最大的權(quán)值。
數(shù)據(jù)范圍：
2 <= n <= 10^6 ， 0 < 序列內(nèi)的數(shù) <= 10^6 。
Input
第一行輸入一個 T，表示有 T 組數(shù)據(jù)。
接下來有 T 組數(shù)據(jù)，每組數(shù)據(jù)的第一行輸入一個數(shù) n ，第二行輸入 n 個數(shù)。
Output
每組數(shù)據(jù)輸出可能的最大的權(quán)值。
Sample Input
1
3
1 2 3
Sample Output
2
解題報告：
簽到題，代碼：
#include<iostream>
#include<string.h>
#include<math.h>
using?namespace?std;
int?a[1000010];
int?main()
{
??int?t;
??cin>>t;
??while(t--)
??{
?? int?maxn=0;int?k,n;
?? memset(a,0,sizeof(a));
?? cin>>n;
?? for(int?i=1;i<=n;i++){
??
?? cin>>a[i];
?? if(a[i]>maxn)
?? {
?? maxn=a[i];
?? k=i;
??}
??
??
????????????????????????}
????int?k2;
????if(k!=1&&k!=n)
????k2=min(a[1],a[n]);
????else?if(k==a[1])
????{
????
???? k2=a[n];
????
}
else
k2=a[1];
cout<<maxn-k2<<endl;
??}
return?0;
}
?
1009
?
MDD的隨機數(shù)
Time Limit : 3000/1000ms (Java/Other)???Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 61???Accepted Submission(s) : 28
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
MDD隨機生成了n(n<le5)個隨機數(shù)x(x<=1e9),
這n個隨機數(shù)排成一個序列，MDD有q(q<=le5)個詢問，
每個詢問給你一個a，問你這個序列中有多少個區(qū)間的最大公約數(shù)不為a
Input
第一行輸入一個T,表示T組測試樣例
每組樣例包含一個n,表示n個隨機數(shù)
再輸入一個Q，表示Q個詢問
每個詢問輸入一個a
Output
每個詢問輸出有多少個區(qū)間的gcd不為a
Sample Input
1
5
1 2 4 4 1
4
1
2
3
4
Sample Output
6
12
15
12
題解：考慮到如果固定區(qū)間左端點L，那么右端點從L+1變化到n的過程中g(shù)cd最多變化logn次（因為每次變化至少除以2）,那么我們就可以枚舉左端點，然后每次二分值連續(xù)的區(qū)間，然后都存到map里,只需要將所有的區(qū)間個數(shù)減去區(qū)間gcd=x的個數(shù)就是本題的答案
代碼：#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<bitset>
#include<set>
#include<map>
using namespace std;
#define LL long long
#define pi (4*atan(1.0))
#define eps 1e-8
#define bug(x)? cout<<"bug"<<x<<endl;
const int N=1e3+10,M=7e6+10,inf=1e9+10,MOD=10;
const LL INF=1e18+10;
?
int a[N];
map<int,LL>dp[N],ans;
map<int,LL>::iterator it;
int main()
{
??? int n,T;
??? scanf("%d",&T);
??? while(T--)
??? {
??????? scanf("%d",&n);
??????? ans.clear();
??????? for(int i=1;i<=n;i++)
??????????? dp[i].clear();
??????? for(int i=1;i<=n;i++)
???????? ???scanf("%d",&a[i]);
??????? for(int i=1;i<=n;i++)
??????? {
??????????? dp[i][a[i]]++;
??????????? ans[a[i]]++;
??????????? for(it=dp[i-1].begin();it!=dp[i-1].end();it++)
??????????? {
??????????????? int x=it->first;
??????????????? LL z=it->second;
?? ?????????????int now=__gcd(x,a[i]);
??????????????? dp[i][now]+=z;
??????????????? ans[now]+=z;
??????????? }
??????? }
??????? LL sum=1LL*n*(n+1)/2;
??????? int q;
??????? scanf("%d",&q);
??????? while(q--)
??????? {
??????????? int x;
??????????? scanf("%d",&x);
??????????? printf("%lld\n",sum-ans[x]);
??????? }
??? }
??? return 0;
}
1010
QAQ
Time Limit : 3000/1000ms (Java/Other)???Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 1082???Accepted Submission(s) : 223
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
定義操作：將數(shù) n 變?yōu)?f(n) = floor(sqrt(n))。即對一個數(shù)開平方后，再向下取整。
如對 2 進行一次操作，開平方再向下取整, 1.414213562..... = 1 , 即變?yōu)榱?1 。
現(xiàn)在給出一個數(shù) n，如果能在 5 次操作內(nèi)把 n 變?yōu)?1，則輸出操作次數(shù)；如果則超過5次輸出"QAQ"。
數(shù)據(jù)范圍：
1<= n <= 10^100
Input
多組輸入，每行輸入一個數(shù) ｎ。
Output
每組數(shù)據(jù)輸出要多少次操作，或者輸出"QAQ"
Sample Input
233
233333333333333333333333333333333333333333333333333333333
Sample Output
3
QAQ
?
解題報告：簽到題，大數(shù)
代碼：
#include?<iostream>
#include?<cstdio>
#include?<cmath>
#include<string.h>
using?namespace?std;
int?main()
{
char?str[1000005];
?long?long?n;
?while(cin>>str)
?{??
????double?ant=0;
????
? int?len=strlen(str);
? if(len>10)
? cout<<"QAQ"<<endl;
? else
? {
? for(int?i=0;i<len;i++)
? {
? ant=ant*10+str[i]-'0';
?}
?int?flag=0;
?while(ant!=1)
?{
? ant=?floor(sqrt(ant));
? flag++;
?}
?if(flag>5)
?cout<<"QAQ"<<endl;
?else
?cout<<flag<<endl;
?}
?}
?
????return?0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/xiechenxi/p/7932122.html
總結(jié)
以上是生活随笔為你收集整理的华东交通大学2017年ACM双基程序设计大赛题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java Set接口详细讲解 TreeS
- 下一篇： Qt之格栅布局（QGridLayout）