Hướng dẫn giải của Tổng vector
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; fo=''; max=1500; maxs=32767; var n,m,re,t,m1,m2,i,j,x,y,xt,yt:longint; a:array[0..29,0..1] of longint; b:array[0..14,0..1] of longint; p:array[0..15] of longint; f:array[0..maxs,0..1] of integer; d:array[-max..max,-max..max] of integer; procedure rf; var i,n:longint; begin assign(input,fi); reset(input); readln(n); p[0]:=1; for i:=1 to 15 do p[i]:=p[i-1] shl 1; m:=n div 2; for i:=0 to m-1 do readln(a[i,0],a[i,1]); for i:=m to n-1 do readln(b[i-m,0],b[i-m,1]); read(x,y); dec(m); m1:=p[m+1]-1; m2:=p[n-n div 2]-1; close(input); end; procedure wf; begin assign(output,fo); rewrite(output); write(re); close(output); end; begin rf; re:=0; d[0,0]:=1; for i:=1 to m1 do begin t:=i; j:=0; while t>0 do begin if t and 1=1 then begin f[i,0]:=f[i,0]+a[j,0]; f[i,1]:=f[i,1]+a[j,1]; end; inc(j); t:=t shr 1; end; inc(d[f[i,0],f[i,1]]); end; for i:=0 to m2 do begin t:=i; j:=0; xt:=0; yt:=0; while t>0 do begin if t and 1=1 then begin xt:=xt+b[j,0]; yt:=yt+b[j,1]; end; inc(j); t:=t shr 1; end; if (abs(x-xt)<=max) and (abs(y-yt)<=max) then re:=re+d[x-xt,y-yt]; end; wf; end.
Code mẫu của happyboy99x
#include<cstdio> #include<map> using namespace std; typedef pair<int, int> ii; #define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i) int x[33], y[33], n, a, b, u, v; map<ii, int> m1, m2; void backtrack(map<ii, int> &m, int begin, int end) { if(begin == end) ++m[ii(a, b)]; else { for(int mul = 0; mul < 2; ++mul) { a += mul * x[begin]; b += mul * y[begin]; backtrack(m, begin + 1, end); a -= mul * x[begin]; b -= mul * y[begin]; } } } int main() { scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%d%d", x+i, y+i); scanf("%d%d", &u, &v); backtrack(m1, 0, n/2); backtrack(m2, n/2, n); long long res = 0; TR(m1, it) { ii f = ii(u - it->first.first, v - it->first.second); if(m2.count(f)) res += (long long) it->second * m2[f]; } printf("%lld\n", res); return 0; }
Code mẫu của ladpro98
program vectorspoj; uses math; type vector = record x,y:longint; end; const maxN = 30; maxV = 50*maxN; fi = ''; var a,arr1:array[1..maxN] of vector; f:array[-maxV..maxV,-maxV..maxV] of longint; n,u,v,limit,d,res:longint; procedure input; var inp:text; i:longint; begin assign(inp,fi); reset(inp); readln(inp,n); for i:=1 to n do readln(inp,a[i].x,a[i].y); readln(inp,u,v); close(inp); end; procedure back(i,x,y:longint); begin if i>limit then begin inc(d); arr1[d].x:=x; arr1[d].y:=y; exit; end; back(i+1,x,y); back(i+1,x+a[i].x,y+a[i].y); end; procedure sinh(i,x,y:longint); begin if i>limit then begin inc(f[x,y]); exit; end; sinh(i+1,x,y); sinh(i+1,x+a[i].x,y+a[i].y); end; procedure process; var i,j:longint; begin for i:=1 to d do begin inc(res,f[u-arr1[i].x,v-arr1[i].y]); end; end; begin input; limit:=n div 2; back(1,0,0); limit:=n; sinh(n div 2+1,0,0); process; write(res); end. begin input; dp; write(f[u,v]); end.
Code mẫu của RR
{$R+,Q+} const FINP=''; FOUT=''; MAXN=30; MAX=32768; type vector=record x,y:longint; end; arr=array[1..MAX] of vector; var n,u,v:longint; kq:int64; a:array[1..MAXN] of vector; sum:array[1..2] of arr; d:array[1..2,1..MAX] of longint; sl:array[1..2] of longint; procedure inp; var f:text; i,sum:longint; begin assign(f,FINP); reset(f); read(f,n); for i:=1 to n do with a[i] do read(f,x,y); read(f,u,v); close(f); sum:=0; for i:=1 to n do sum:=sum+abs(a[i].x); if sum<abs(u) then begin writeln(0); halt; end; sum:=0; for i:=1 to n do sum:=sum+abs(a[i].y); if sum<abs(v) then begin writeln(0); halt; end; end; procedure ans; var f:text; begin assign(f,FOUT); rewrite(f); writeln(f,kq); close(f); end; procedure lietke(l,r,s:longint); var x,y:longint; procedure visit(i:longint); var j:longint; begin for j:=0 to 1 do begin if j=1 then begin x:=x+a[i+l].x; y:=y+a[i+l].y; end; if i<r-l then visit(i+1) else begin inc(sl[s]); sum[s,sl[s]].x:=x; sum[s,sl[s]].y:=y; end; if j=1 then begin x:=x-a[i+l].x; y:=y-a[i+l].y; end; end; end; begin x:=0; y:=0; sl[s]:=0; visit(0); end; procedure swap(var a,b:longint); var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure qsort(s:longint); var i,j:longint; procedure sort(l,r:longint); var i,j,mx,my:longint; begin i:=l; j:=r; with sum[s,(i+j) shr 1] do begin mx:=x; my:=y; end; repeat while (sum[s,i].x<mx) or ((sum[s,i].x=mx) and (sum[s,i].y<my)) do inc(i); while (sum[s,j].x>mx) or ((sum[s,j].x=mx) and (sum[s,j].y>my)) do dec(j); if i<=j then begin swap(sum[s,i].x,sum[s,j].x); swap(sum[s,i].y,sum[s,j].y); inc(i); dec(j); end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; begin sort(1,sl[s]); j:=1; d[s,1]:=1; for i:=2 to sl[s] do if (sum[s,i].x>sum[s,j].x) or ((sum[s,i].x=sum[s,j].x) and (sum[s,i].y>sum[s,j].y)) then begin inc(j); d[s,j]:=1; sum[s,j]:=sum[s,i]; end else inc(d[s,j]); sl[s]:=j; end; function find(u,v,l,r:longint):longint; var mid:longint; begin if l>r then exit(0); if (u<sum[1,l].x) or ((u=sum[1,l].x) and (v<sum[1,l].y)) then exit(0); if (u>sum[1,r].x) or ((u=sum[1,r].x) and (v>sum[1,r].y)) then exit(0); if (u=sum[1,l].x) and (v=sum[1,l].y) then exit(l); if (u=sum[1,r].x) and (v=sum[1,r].y) then exit(r); mid:=(l+r) shr 1; if (u=sum[1,mid].x) and (v=sum[1,mid].y) then exit(mid); if (u<sum[1,mid].x) or ((u=sum[1,mid].x) and (v<sum[1,mid].y)) then exit(find(u,v,1,mid-1)) else exit(find(u,v,mid+1,r)); end; procedure solve; var i,k:longint; begin for i:=1 to sl[2] do begin k:=find(u-sum[2,i].x,v-sum[2,i].y,1,sl[1]); if k>0 then kq:=kq+int64(d[2,i])*d[1,k]; end; end; begin inp; kq:=0; lietke(1,n shr 1,1); qsort(1); lietke(n shr 1+1,n,2); qsort(2); solve; ans; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> #define k 1500 int f[2*k+3][2*k+3]; int main() { // freopen("VECTOR.in","r",stdin); int n,x[31],y[31],X,Y; for(int i = 0;i<=2*k;i++) for(int j = 0;j<=2*k;j++) f[i][j]=0; scanf("%d",&n); for(int i = 1;i<=n;i++) { scanf("%d",&x[i]); scanf("%d",&y[i]); } scanf("%d %d",&X,&Y); if(X>30000 || X<-30000 || Y>30000 || Y<-30000) { printf("0"); } else { int u[20];u[0]=1; for(int i = 1;i<=18;i++) u[i] = u[i-1]*2; int K = u[n/2]-1,M = u[n-n/2]-1; //printf("%d %d %d\n",n,K,M); //printf("************\n"); for(int i = 0;i<=K;i++) { int N = i,tongx=0,tongy=0; for(int j = 1;j<=n/2;j++) { if(N%2==1) { tongx=tongx+x[j]; tongy = tongy + y[j]; } N = N/2; } // printf("%d %d\n",tongx,tongy); f[tongx+k][tongy+k]++; } int KQ = 0; for(int i = 0;i<=M;i++) { int N = i,tongx=0,tongy=0; for(int j = 1;j<=n-n/2;j++) { if(N%2==1) { tongx=tongx+x[j+n/2]; tongy = tongy + y[j+n/2]; } N = N/2; } if(X-tongx<=1500 && X-tongx>=-1500 && Y-tongy<=1500 && Y-tongy>=-1500) KQ = KQ + f[X-tongx+k][Y-tongy+k]; } printf("%d",KQ); } // getch(); }
Code mẫu của ll931110
{$MODE DELPHI} program VECTOR; const input = ''; output = ''; maxn = 30; maxv = 100; maxs = maxn * maxv div 2; type rec = record x,y: integer; end; var a: array[1..maxn] of rec; left: array[0..(1 shl (maxn div 2)) - 1] of rec; p: array[-maxs..maxs,-maxs..maxs] of integer; s: array[0..maxn] of integer; ux,uy,sx,sy,n,count: integer; procedure init; var f: text; i: integer; begin assign(f, input); reset(f); readln(f, n); for i := 1 to n do readln(f, a[i].x, a[i].y); readln(f, ux, uy); close(f); end; procedure precalc; var i,j,t: integer; begin left[0].x := 0; left[0].y := 0; for i := 1 to (1 shl (n div 2)) - 1 do for j := 1 to n div 2 do if i and (1 shl (j - 1)) = (1 shl (j - 1)) then begin t := i xor (1 shl (j - 1)); left[i].x := left[t].x + a[j].x; left[i].y := left[t].y + a[j].y; end; end; procedure attempt(i: integer); var j: integer; begin for j := s[i - 1] + 1 to n do begin sx := sx + a[j].x; sy := sy + a[j].y; inc(p[sx,sy]); s[i] := j; if j < n then attempt(i + 1); sx := sx - a[j].x; sy := sy - a[j].y; end; end; function valid(kx,ky: integer): boolean; begin valid := (abs(kx) <= maxs) and (abs(ky) <= maxs); end; procedure solve; var i,kx,ky: integer; begin precalc; sx := 0; sy := 0; fillchar(p, sizeof(p), 0); p[0,0] := 1; s[0] := n div 2; attempt(1); for i := 0 to (1 shl (n div 2)) - 1 do begin kx := ux - left[i].x; ky := uy - left[i].y; if valid(kx,ky) then count := count + p[kx,ky]; end; end; procedure printresult; var f: text; begin assign(f, output); rewrite(f); writeln(f, count); close(f); end; begin init; solve; printresult; end.
Code mẫu của skyvn97
#include<stdio.h> #include<vector> #include<map> using namespace std; typedef pair<int,int> ii; typedef map<ii,int> mii; typedef vector<ii> vii; mii a; vii va,vb,sb; int n; ii v,s; int x[22]; void init(void) { scanf("%d",&n); int i,x,y; for (i=1;i<=n/2;i=i+1) { scanf("%d",&x); scanf("%d",&y); va.push_back(ii(x,y)); } for (i=n/2+1;i<=n;i=i+1) { scanf("%d",&x); scanf("%d",&y); vb.push_back(ii(x,y)); } scanf("%d",&x); scanf("%d",&y); v=ii(x,y); } void btrka(int k) { int i; for (i=0;i<=1;i=i+1) { x[k]=i; s=ii(s.first+i*va[k].first,s.second+i*va[k].second); if (k==va.size()-1) a[s]++; else btrka(k+1); s=ii(s.first-i*va[k].first,s.second-i*va[k].second); } } void btrkb(int k) { int i; for (i=0;i<=1;i=i+1) { x[k]=i; s=ii(s.first+i*vb[k].first,s.second+i*vb[k].second); if (k==vb.size()-1) sb.push_back(s); else btrkb(k+1); s=ii(s.first-i*vb[k].first,s.second-i*vb[k].second); } } void process(void) { s=ii(0,0); btrka(0); s=ii(0,0); btrkb(0); int i; int cnt; cnt=0; for (i=0;i<sb.size();i=i+1) cnt=cnt+a[ii(v.first-sb[i].first,v.second-sb[i].second)]; printf("%d",cnt); } int main(void) { init(); process(); }
Code mẫu của khuc_tuan
#include <iostream> #include <map> using namespace std; int n; pair<int,int> a[33]; pair<int,int> S; pair<int,int> operator+(pair<int,int> a, pair<int,int> b) { return make_pair(a.first+b.first,a.second+b.second); } pair<int,int> operator-(pair<int,int> a, pair<int,int> b) { return make_pair(a.first-b.first,a.second-b.second); } int main() { scanf("%d", &n); for(int i=0;i<n;++i) scanf("%d%d", &a[i].first, &a[i].second); scanf("%d%d", &S.first, &S.second); if(n<=15) { int dem = 0; for(int b=0;b<(1<<n);++b) { pair<int,int> z = make_pair(0,0); for(int i=0;i<n;++i) if((b&(1<<i))!=0) z = z + a[i]; if(z==S) ++dem; } printf("%d\n", dem); } else { int k = n/2; map<pair<int,int>,int> ma; for(int b=0;b<(1<<k);++b) { pair<int,int> z = make_pair(0,0); for(int i=0;i<k;++i) if((b&(1<<i))!=0) z = z + a[i]; ma[z] ++ ; } k = n - k; int dem = 0; for(int b=0;b<(1<<k);++b) { pair<int,int> z = make_pair(0,0); for(int i=0;i<k;++i) if((b&(1<<i))!=0) z = z + a[n-1-i]; dem += ma[S-z]; } cout << dem << endl; } return 0; }
Bình luận