江西理工摸底测试题解报告

A：开两个数组s、r，s存容量，r存放了多少。用一个中间值temp来记录当前多出的水，两种情况，一种满了输出 s[ i ]，多余的放 temp 里，另一种没满输出 r[ i ] + temp。

AC代码：

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=100005;
void sol(){
int n,m;
cin>>n>>m;
ll s[N],r[N];
memset(s,0,sizeof(s));
memset(r,0,sizeof(r));
for(int i=1;i<=n;i++){
cin>>s[i];
}
int x,y;
for(int i=1;i<=m;i++){
cin>>x>>y;
r[x]+=y;
}
ll temp=0;
for(int i=1;i<=n;i++){
if(r[i]+temp>=s[i]){
temp=r[i]+temp-s[i];
cout<<s[i];
}
else{
cout<temp;
temp=0;
}
if(i!=n) cout<<" ";
else cout<<endl;
}
}
int main(){
int t;
cin>>t;
while(t--) sol();
return 0;
}

Water

B：先找出40000以内的素数，放在一个数组ve里，并标记40000以内的数组。两遍循环，第二个大于等于第一个数，第三个数就是n-ve[ i ] - ve[ j ]，判断第三个数大于第二个且是素数则 ans++。这里的标记用map存超时了，有点迷。（现在懂了，map的每次查询时间要logN，叠加起来就超时了）。

AC代码：

1 #include
2 #include
3 #include
4 #include
5 #include

Prime Split

C：因为连接两个顶点u">u和v">v的花费是MIN(|Xu&＃x2212;Xv|,|Yu&＃x2212;Yv|,|Zu&＃x2212;Zv|)">MIN(|Xu−Xv|,|Yu−Yv|,|Zu−Zv|)，则将每个顶点的x，y，z分别排序，相邻的点建边，记录下每一条边的端点，再将得到的3n-3条边由小到大排序，边长由小到大开始建图，即 kruskal 算法。

AC代码：

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 typedef long long ll;
7 const ll N=2e5+10;
8 ll n,num=1,fa[N];
9 struct node{
10 ll from,to;
11 ll dis;
12 }edge[N*3];
13 struct tt{
14 ll x;
15 ll t;
16 }xyz[N*3];
17 bool cmpx(tt a,tt b){return a.x<b.x;}
18 bool cmp(node a,node b){return a.dis<b.dis;}
19 ll father(ll x){
20 if(fa[x]==x) return x;
21 else return fa[x]=father(fa[x]); //这里一开始直接返回father(fa[x])就疯狂超时，爆炸
22 }
23 void unionn(ll x,ll y){
24 fa[father(x)]=father(y);
25 }
26 void sol(){
27 cin>>n;
28 for(ll i=1;i<=n;i++){
29 cin>>xyz[i].x>>xyz[n+i].x>>xyz[2*n+i].x;
30 xyz[i].t=xyz[i+n].t=xyz[i+2*n].t=i;
31 }
32 sort(xyz+1,xyz+n+1,cmpx);
33 for(ll i=2;i<=n;i++){
34 edge[num].dis=xyz[i].x-xyz[i-1].x;
35 edge[num].from=xyz[i-1].t;
36 edge[num++].to=xyz[i].t;
37 }
38 sort(xyz+n+1,xyz+n+n+1,cmpx);
39 for(ll i=n+2;i<=2*n;i++){
40 edge[num].dis=xyz[i].x-xyz[i-1].x;
41 edge[num].from=xyz[i-1].t;
42 edge[num++].to=xyz[i].t;
43 }
44 sort(xyz+n+n+1,xyz+n+n+n+1,cmpx);
45 for(ll i=2+n+n;i<=3*n;i++){
46 edge[num].dis=xyz[i].x-xyz[i-1].x;
47 edge[num].from=xyz[i-1].t;
48 edge[num++].to=xyz[i].t;
49 }
50 for(ll i=1;i<=n;i++) fa[i]=i;
51 sort(edge+1,edge+num,cmp);
52 ll ans=0,cnt=0;
53 for(ll i=1;i){
54 if(father(edge[i].from) != father(edge[i].to)){
55 unionn(edge[i].from,edge[i].to);
56 ans+=edge[i].dis;
57 cnt++;
58 }
59 if(cnt==n-1) break;
60 }
61 cout<<ans;
62 }
63 int main(){
64 sol();
65 return 0;
66 }

connect

D：数位dp，dp[ i ][ j ]表示有 i 位数时且最后一位为 j 时的情况。dp[ i ][ j ]=sum (dp[ i-1][ 0~k]) - sum ( dp[ i-1][max (j-c ,0) ~ min (j+c,k)]  )  )（开始时k--了，方便运算）。

AC代码：

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 typedef long long ll;
7 const ll mod=1e9+7;
8 ll n,k,c;
9 ll dp[1005][1005];
10 void sol(){
11 cin>>n>>k>>c;
12 k--;
13 memset(dp,0,sizeof(dp));
14 if(n==1){
15 cout<1<<endl;
16 return ;
17 }
18 dp[1][0]=0;
19 for(ll i=1;i<=k;i++) dp[1][i]=1;
20 ll pre=k,temp,now;
21 for(ll i=2;i<=n;i++){
22 now=0;
23 for(ll j=0;j<=k;j++){
24 temp=0;
25 for(ll l=max(j-c, (ll)0 );l<=min(j+c,k);l++)
26 temp+=dp[i-1][l];
27 dp[i][j]=(pre-temp+mod)%mod; //不加mod可能会有负数出现
28 now+=dp[i][j];
29 }
30 pre=now;
31 }
32 ll ans=0;
33 for(ll i=0;i<=k;i++) ans=(ans+dp[n][i])%mod;
34 cout<endl;
35 }
36 int main(){
37 ll t;
38 cin>>t;
39 while(t--) sol();
40 return 0;
41 }

数位dp

E：拆分n，举例，4=2+2，5=2+3，6=3+3，7=3+2+2，8=3+3+2，9=3+3+3。。。可以得到规律，尽量多分3，不能分出1。对于 (1/n)%x ，因为 x 与 你互质，所以可以得出就是求 n 与 x 的逆元。

设k是n对x的逆元，则 n*k%x=1；（1/n）%x =（（1/n）%x）*（n*k）%x =（（1/n）*n*k）%x = k%x。就变成了求n和x的逆元的问题了

AC代码：

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 typedef long long ll;
7 void extend_gcd(ll a,ll b,ll &x,ll &y){
8 if(b==0){
9 x=1,y=0;
10 return ;
11 }
12 extend_gcd(b,a%b,x,y);
13 ll tmp = x;
14 x = y;
15 y = tmp - (a/b)*y;
16 }
17 ll mod_inverse(ll a,ll m){ //逆元
18 ll x,y;
19 extend_gcd(a,m,x,y);
20 return (m+x%m)%m; //x可能是负数
21 }
22 int main(){
23 ll n,N;
24 cin>>n;
25 int t=n%3;
26 if(t==1){
27 N=4;
28 t=n-4;
29 }
30 else if(t==2){
31 N=2;
32 t=n-2;
33 }
34 else{
35 N=1;
36 t=n;
37 }
38 for(int i=3;i<=t;i+=3) N*=3;
39 cout<N;
40 }

Number

 F：线段树模板题，树状数组也是模板题：

AC代码：

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 typedef long long ll;
7 const int N=100005;
8 int n,m;
9 struct node{
10 int l,r;
11 ll sum;
12 int lazy;
13 int len;
14 }T[N<<2];
15 void push_down(int rt){
16 T[rt <<1].sum += T[rt].lazy * T[rt <<1].len;
17 T[rt <<1 | 1].sum += T[rt].lazy * T[rt <<1 | 1].len;
18 T[rt <<1].lazy += T[rt].lazy;
19 T[rt <<1 | 1].lazy += T[rt].lazy;
20 T[rt].lazy=0;
21 }
22 void push_up(int rt){
23 T[rt].sum=T[rt<<1].sum+T[rt<<1|1].sum;
24 }
25 void build(int l,int r,int rt){
26 T[rt].l=l;
27 T[rt].r=r;
28 T[rt].lazy=0;
29 T[rt].len=r-l+1;
30 if(l == r){
31 T[rt].sum=0;
32 return ;
33 }
34 int mid=(l+r)>>1;
35 build(l,mid,rt<<1);
36 build(mid+1,r,rt<<1|1);
37 push_up(rt);
38 }
39
40 void update(int l,int r,int val,int rt){
41 if(T[rt].l==l&&T[rt].r==r){
42 T[rt].sum+=T[rt].len*val;
43 T[rt].lazy+=val;
44 return ;
45 }
46 if(T[rt].lazy) push_down(rt);
47 int mid=(T[rt].l+T[rt].r)>>1;
48 if(mid>=r) update(l,r,val,rt<<1);
49 else if(l>mid) update(l,r,val,rt<<1|1);
50 else{
51 update(l,mid,val,rt<<1);
52 update(mid+1,r,val,rt<<1|1);
53 }
54 push_up(rt);
55 }
56
57 int query(int t,int rt){
58 if(T[rt].l==t&&T[rt].r==t) return T[rt].sum;
59 if(T[rt].lazy) push_down(rt);
60 int mid=(T[rt].l+T[rt].r)>>1;
61 if(mid>=t) return query(t,rt<<1);
62 else return query(t,rt<<1|1);
63 }
64
65 void sol(){
66 build(1,n,1);
67 while(m--){
68 int s;
69 scanf("%d",&s);
70 if(s == 2){
71 int x;
72 scanf("%d",&x);
73 cout<<(1&(query(x, 1)))<<endl;
74 }
75 else{
76 int x,y;
77 scanf("%d%d",&x,&y);
78 update( x, y, 1, 1);
79 }
80 }
81 }
82 int main(){
83 scanf("%d%d",&n,&m);
84 sol();
85 return 0;
86 }

线段树

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 typedef long long ll;
7 const int N=100005;
8 int n,m;
9 int a[N],c[N];
10 int lowbit(int x){
11 return x&(-x);
12 }
13 void updata(int i,int k){
14 while(i<=n){
15 c[i] += k;
16 i +=lowbit(i);
17 }
18 }
19 int getsum(int i){
20 int res=0;
21 while(i>0){
22 res+=c[i];
23 i -= lowbit(i);
24 }
25 return res;
26 }
27 void sol(){
28 for(int i=1;i<=m;i++){
29 int s;
30 scanf("%d",&s);
31 if(s&1){
32 int x,y;
33 scanf("%d%d",&x,&y);
34 updata(x,1);
35 updata(y+1,-1);
36 }
37 else{
38 int x;
39 scanf("%d",&x);
40 int ans=(1&getsum(x));
41 cout<endl;
42 }
43 }
44 }
45 int main(){
46 cin>>n>>m;
47 sol();
48 return 0;
49 }

树状数组

G：n 个人，每次去k个，有Cnk种去法。每种去法里有x个人送和n-x个人收，一共就有2^k-2种方法。一共就有Cnk*（2^k-2）k从2 到 n。中间要用求逆元，不然会爆long long 。

AC代码：

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 typedef long long ll;
7 const ll mod=1e9+7;
8 ll ans,t[100005],r[100005];
9 void extend_gcd(ll a,ll b,ll &x,ll &y){
10 if(b==0){
11 x=1,y=0;
12 return ;
13 }
14 extend_gcd(b,a%b,x,y);
15 ll tmp = x;
16 x = y;
17 y = tmp - (a/b)*y;
18 }
19 ll mod_inverse(ll a,ll m){
20 ll x,y;
21 extend_gcd(a,m,x,y);
22 return (m+x%m)%m;
23 }
24 void sol(){
25 int n;
26 cin>>n;
27 t[1]=2;ans=0;r[0]=1;
28 for(int i=1;i<=n/2;i++){
29 if((r[i-1]*(n-i+1))%i!=0){
30 ll k=mod_inverse(i,mod);
31 // cout<
32 r[i]=((r[i-1]*(n-i+1))%mod*(k%mod))%mod;
33 }
34 else r[i]=(r[i-1]*(n-i+1)/i)%mod;
35 }
36 for(int i=n;i>n/2;i--)
37 r[i]=r[n-i];
38 // for(int i=0;i<=n;i++) cout<
39 for(int i=2;i<=n;i++){
40 t[i]=(t[i-1]*2)%mod;
41 ans=((t[i]-2)*r[i]+ans)%mod;
42 }
43 cout<<ans;
44 }
45 int main(){
46 sol();
47 return 0;
48 }

聚会

H：bfs先跑一遍第一种图，得到最短的路径距离x1，再将第二个图的障碍物叠加到图一，再跑一遍，得到最短路径x2，若x1==x2，则有相同最短路径，否则无。

AC代码：

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7 typedef long long ll;
8 const int N=505;
9 int fx[4][2]={1,0,0,1,-1,0,0,-1};
10 int sx,sy,rx,ry,n,m;
11 char a[N][N],b[N][N];
12 int c1[N][N],c2[N][N];
13 struct tt{
14 int x,y,cd;
15 };
16 queueq;
17 int bfs1(){
18 tt A,B;
19 A.x=sx;A.y=sy;A.cd=0;
20 c1[0][0]=1;
21 q.push(A);
22 while(q.size()){
23 A=q.front();
24 q.pop();
25 if(A.x==rx&&A.y==ry){
26 return A.cd;
27 }
28 for(int i=0;i<4;i++){
29 B.x=A.x+fx[i][0];
30 B.y=A.y+fx[i][1];
31 if(a[B.x][B.y]=='#'||B.x<0||B.y<0||B.x>=n||B.y>=m||c1[B.x][B.y]) continue;
32 B.cd=A.cd+1;
33 c1[B.x][B.y]=1;
34 q.push(B);
35 // cout<
36 }
37 }
38 return 500000;
39 }
40 queuep;
41 int bfs2(){
42 tt A,B;
43 A.x=sx;A.y=sy;A.cd=0;
44 c2[0][0]=1;
45 p.push(A);
46 while(!p.empty()){
47 A=p.front();
48 p.pop();
49 if(A.x==rx&&A.y==ry){
50 return A.cd;
51 }
52 for(int i=0;i<4;i++){
53 B.x=A.x+fx[i][0];
54 B.y=A.y+fx[i][1];
55 if(b[B.x][B.y]=='#'||B.x<0||B.y<0||B.x>=n||B.y>=m||c2[B.x][B.y]) continue;
56 B.cd=A.cd+1;
57 c2[B.x][B.y]=1;
58 p.push(B);
59 }
60 }
61 return 500000;
62 }
63 void sol(){
64 cin>>n>>m;
65 sx=0;sy=0;rx=n-1;ry=m-1;
66 for(int i=0;i)
67 for(int j=0;j)
68 cin>>a[i][j];
69 int cd1=bfs1();
70 for(int i=0;i)
71 for(int j=0;j){
72 cin>>b[i][j];
73 if(a[i][j]=='#') b[i][j]='#';
74 }
75 int cd2=bfs2();
76 if(cd1==cd2&&cd1!=500000) cout<<"YES";
77 else cout<<"NO";
78 }
79 int main(){
80 sol();
81 return 0;
82 }

地图

I：从第一个字符遍历到中间字符，与对称的字符比较，不相等更大的变成更小的，相等跳过

AC代码：

1 I#include
2 #include
3 #include
4 #include
5 using namespace std;
6 typedef long long ll;
7 void sol(){
8 string s;
9 cin>>s;
10 int n=s.size();
11 for(int i=0;i2;i++){
12 if(s[i]==s[n-i-1]) continue;
13 else{
14 if(s[i]1]) s[n-i-1]=s[i];
15 else s[i]=s[n-i-1];
16 }
17 }
18 cout<<s;
19 }
20 int main(){
21 sol();
22 return 0;
23 }

签到

MIN(|Xu&＃x2212;Xv|,|Yu&＃x2212;Yv|,|Zu&＃x2212;Zv|)">