USACO 6.4 章节
The Primes
题目大意
5*5
矩阵,给定左上角
要所有行
,列
,从左向右看对角线
为质数,没有前导零,且这些质数数位和
相等(题目给和)
按字典序输出所有方案。。。
题解
看上去就是个 无脑暴搜
题目条件翻译成处理
或剪枝
- 按照 字典序顺序搜,
- 末位是奇数
- 和确定了,那么前4位的和的奇偶性确定了
- 数值是5位数,可以先生成质数表
- 和-前n位和 小于 9乘剩余位数
也许先把第一行和第一列定下,然后按照数位和 再分组质数,搜索量会超级小?
17 7
的这组数据 超过5s (i7-7700HQ
)
#include <bits/stdc++.h> #define rep(i,a,n) for (long long i=a;i<n;i++) #define per(i,a,n) for (long long i=n-1;i>=a;i--) using namespace std; const string filename = "prime3"; void usefile(){ freopen((filename+".in").c_str(),"r",stdin); freopen((filename+".out").c_str(),"w",stdout); } int A[10][10]; int p[100010]; int s; bool check(int idxi,int idxj){ { int sum = 0; rep(i,0,idxi+1){ sum+=A[i][idxj]; } if(sum > s){ return false; } if( (s-sum) > (4-idxi)*9 ){ return false; } if(idxi == 0 && sum == 0){ return false; } if(idxi == 4){ if(sum != s){ return false; } int v = 0; rep(i,0,5){ v*=10; v+=A[i][idxj]; } if(p[v]){ return false; } } if(idxi == 3 && (s-sum)%2 == 0){ return false; } } { int sum = 0; rep(j,0,idxj+1){ sum+=A[idxi][j]; } if(sum > s){ return false; } if( (s-sum) > (4-idxj)*9 ){ return false; } if(idxj == 0 && sum == 0){ return false; } if(idxj == 4){ if(sum != s){ return false; } int v = 0; rep(j,0,5){ v*=10; v+=A[idxi][j]; } if(p[v]){ return false; } } if(idxj == 3 && (s-sum)%2 == 0){ return false; } } { // 左下到右上 if(idxi+idxj == 4){ int sum = 0; rep(i,0,idxi+1){ sum+=A[i][4-i]; } if(sum > s){ return false; } if( (s-sum) > (4-idxi)*9 ){ return false; } if(idxi == 4){ if(sum != s){ return false; } int v = 0; per(i,0,5){ v*=10; v+=A[i][4-i]; } if(p[v]){ return false; } } } } { // 左上到右下 if(idxi-idxj == 0){ int sum = 0; rep(i,0,idxi+1){ sum+=A[i][i]; } if(sum > s){ return false; } if( (s-sum) > (4-idxi)*9 ){ return false; } if(idxi == 4){ if(sum != s){ return false; } int v = 0; rep(i,0,5){ v*=10; v+=A[i][i]; } if(p[v]){ return false; } } if(idxj == 3 && (s-sum)%2 == 0){ return false; } } } return true; } void print(){ static bool pre_n = false; if(pre_n){ printf("\n"); }else{ pre_n = true; } rep(i,0,5){ rep(j,0,5){ printf("%d",A[i][j]); } printf("\n"); } } void dfs(int pos){ if(pos == 25){ print(); return ; } int idxi = pos/5; int idxj = pos%5; rep(i,0,10){ A[idxi][idxj] = i; if(check(idxi,idxj)){ dfs(pos+1); } } } void init(){ rep(i,2,100000){ if(!p[i]){ for(long long j = i*i;j<100000;j+=i){ p[j] = 1; } } } } int main(){ usefile(); init(); cin>>s>>A[0][0]; dfs(1); return 0; }
根据和来看看个数得到 和:个数
4:4 5:12 7:28 8:45 10:95 11:143 13:236 14:272 16:411 17:479 19:630 20:664 22:742 23:757 25:741 26:706 28:580 29:528 31:379 32:341 34:205 35:166 37:84 38:62 40:34 41:13 43:4 44:2
相对于原来 的搜索空间 小了很多
改完以后 第6个点超时: 17 1
#include <bits/stdc++.h> #define rep(i,a,n) for (long long i=a;i<n;i++) #define per(i,a,n) for (long long i=n-1;i>=a;i--) using namespace std; const string filename = "prime3"; void usefile(){ freopen((filename+".in").c_str(),"r",stdin); freopen((filename+".out").c_str(),"w",stdout); } int A[10][10]; int p[100010]; map<int,vector<int>>sum2v; set<string>ss; int s; void print(){ string news = ""; rep(i,0,5){ rep(j,0,5){ news += ('0'+A[i][j]); } news += '\n'; } ss.insert(news); return ; static bool pre_n = false; if(pre_n){ printf("\n"); }else{ pre_n = true; } rep(i,0,5){ rep(j,0,5){ printf("%d",A[i][j]); } printf("\n"); } } void check(){ int ncnt = 0; int sum = 0; per(i,0,5){ sum*=10; sum+=A[i][4-i]; ncnt+=A[i][4-i]; } if(ncnt != s)return; if(p[sum])return; int sum0=0; int ncnt0=0; rep(i,0,4){ sum0+=A[i][i]; sum0*=10; ncnt0+=A[i][i]; } int sum1=0; int ncnt1=0; rep(j,0,4){ sum1+=A[4][j]; sum1*=10; ncnt1+=A[4][j]; } int sum2=0; int ncnt2=0; rep(i,0,4){ sum2+=A[i][4]; sum2*=10; ncnt2+=A[i][4]; } if(ncnt0 != ncnt1 || ncnt0 != ncnt2)return; int i = s - ncnt0; if(i < 0 || i > 10 || i%2 == 0)return ; if((!p[sum0+i]) && (!p[sum1+i]) && (!p[sum2+i])){ // printf("sum:%d\n",sum); A[4][4] = i; print(); } } void dfs(int ij){ if(ij == 4){ check(); return ; } int prerow = 0; int precol = 0; rep(j,0,ij){ prerow *=10; prerow += A[ij][j]; } if(ij == 0){ prerow = A[0][0]; } rep(i,0,ij){ precol += A[i][ij]; precol *=10; } for(auto vrow:sum2v[prerow]){ int pre0 = false; per(j,0,5){ // printf("[%d]%d ==> vrow[%05d]A0[%d][%lld]=%d\n",ij,prerow,vrow,ij,j,vrow%10); A[ij][j]=vrow%10; vrow/=10; if(ij == 0 && A[ij][j] == 0){ pre0 = true; break; } } if(pre0)continue; int pcol = precol+A[ij][ij]; for(auto vcol:sum2v[pcol]){ pre0 = false; per(i,0,5){ // printf("\t[%d] %d ==> vcol[%05d]A1[%lld][%d]=%d\n",ij,pcol,vcol,i,ij,vcol%10); A[i][ij]=vcol%10; vcol/=10; if(ij == 0 && A[i][ij] == 0){ pre0 = true; break; } } if(pre0)continue; dfs(ij+1); } } } void init(){ rep(i,2,100000){ if(!p[i]){ if(i>=10000){ int sum = 0; int ii = i; rep(idx,0,5){ sum+=ii%10; ii/=10; } if(sum == s){ int ii = i; rep(idx,0,5){ sum2v[ii].push_back(i); ii/=10; } } } for(long long j = i*i;j<100000;j+=i){ p[j] = 1; } } } } int main(){ usefile(); cin>>s>>A[0][0]; init(); dfs(0); for(auto item:ss){ static bool pn = false; if(pn){ printf("\n"); }else{ pn = true; } printf("%s",item.c_str()); } return 0; }
再增加一个预先剪枝 依然没过 第6
个点,在我的电脑上1.893s
然后我对 中间的点,进行了预处理(预先判断 左下角到右上角),tle 9
,数据是23 1
,虽然我的电脑上1.099s
然后 把map换成 数组 就本地0.227s
,USACO就过了...
#include <bits/stdc++.h> #define rep(i,a,n) for (long long i=a;i<n;i++) #define per(i,a,n) for (long long i=n-1;i>=a;i--) using namespace std; const string filename = "prime3"; void usefile(){ freopen((filename+".in").c_str(),"r",stdin); freopen((filename+".out").c_str(),"w",stdout); } int A[10][10]; int p[100010]; vector<int>sum2v[100010]; set<string>ss; int s; void print(){ string news = ""; rep(i,0,5){ rep(j,0,5){ news += ('0'+A[i][j]); } news += '\n'; } ss.insert(news); return ; static bool pre_n = false; if(pre_n){ printf("\n"); }else{ pre_n = true; } rep(i,0,5){ rep(j,0,5){ printf("%d",A[i][j]); } printf("\n"); } } void check(){ int ncnt = 0; int sum = 0; per(i,0,5){ sum*=10; sum+=A[i][4-i]; ncnt+=A[i][4-i]; } if(ncnt != s)return; if(p[sum])return; int sum0=0; int ncnt0=0; rep(i,0,4){ sum0+=A[i][i]; sum0*=10; ncnt0+=A[i][i]; } int sum1=0; int ncnt1=0; rep(j,0,4){ sum1+=A[4][j]; sum1*=10; ncnt1+=A[4][j]; } int sum2=0; int ncnt2=0; rep(i,0,4){ sum2+=A[i][4]; sum2*=10; ncnt2+=A[i][4]; } if(ncnt0 != ncnt1 || ncnt0 != ncnt2)return; int i = s - ncnt0; if(i < 0 || i > 10 || i%2 == 0)return ; if((!p[sum0+i]) && (!p[sum1+i]) && (!p[sum2+i])){ // printf("sum:%d\n",sum); A[4][4] = i; print(); } } bool precheck(int ij){ rep(i,ij+1,5){ int pre = 0; rep(j,0,ij+1){ pre*=10; pre+=A[i][j]; } if(!sum2v[pre].size())return false; } rep(j,ij+1,5){ int pre = 0; rep(i,0,ij+1){ pre*=10; pre+=A[i][j]; } if(!sum2v[pre].size())return false; } if(ij == 2){ int sum = 0; int pre = 0; per(i,0,5){ pre*=10; pre+=A[i][4-i]; sum+=A[i][4-i]; } if(s!=sum)return false; if(p[pre])return false; } return true; } void dfs(int ij){ if(ij == 4){ check(); return ; } int prerow = 0; int precol = 0; rep(j,0,ij){ prerow *=10; prerow += A[ij][j]; } if(ij == 0){ prerow = A[0][0]; } rep(i,0,ij){ precol += A[i][ij]; precol *=10; } // A[2][2] if(ij == 2){ int mid = s- A[4][0]-A[3][1]-A[1][3]-A[0][4]; if(mid < 0 || mid > 9)return; int v = A[4][0]*10000+A[3][1]*1000+mid*100+A[1][3]*10+A[0][4]; if(p[v])return;// 左下到右上 prerow = prerow*10+mid; } for(auto vrow:sum2v[prerow]){ int pre0 = false; per(j,0,5){ A[ij][j]=vrow%10; vrow/=10; if(ij == 0 && A[ij][j] == 0){ pre0 = true; break; } } if(pre0)continue; int pcol = precol+A[ij][ij]; for(auto vcol:sum2v[pcol]){ pre0 = false; per(i,0,5){ A[i][ij]=vcol%10; vcol/=10; if(ij == 0 && A[i][ij] == 0){ pre0 = true; break; } } if(pre0)continue; if(!precheck(ij))continue; dfs(ij+1); } } } void init(){ rep(i,2,100000){ if(!p[i]){ if(i>=10000){ int sum = 0; int ii = i; rep(idx,0,5){ sum+=ii%10; ii/=10; } if(sum == s){ int ii = i; rep(idx,0,5){ sum2v[ii].push_back(i); ii/=10; } } } for(long long j = i*i;j<100000;j+=i){ p[j] = 1; } } } } int main(){ usefile(); cin>>s>>A[0][0]; init(); dfs(0); for(auto item:ss){ static bool pn = false; if(pn){ printf("\n"); }else{ pn = true; } printf("%s",item.c_str()); } return 0; }
提交后测试
- 把precheck 去掉, 发现也能过,甚至更快XD,说明其作用 小于 其副作用
- 把
A[2][2]
预处理去掉 会超时第8个点
Electric Fences
题目大意
<=150
条线段(和X 轴或 Y轴平行) , 坐标 范围0<= x,y<=100
求一个点(可以非整数,最多1位小数),从这个点 向每一条线段连出一个线段,使连出的线段长度综合最小,求点坐标和 最小总长度
题解
如果我们得到了一个点,那么 这个点到一条线段做垂线,如果垂线的垂点在线段上那么为这条垂线,否则为点到这条线段其中一个端点的长度
显然 和计算几何有关因为都和坐标轴平行了,完全用不到计算几何
有什么用呢?到所有线段都刚刚是垂线段最好?
显然有反例 (0,0)-(1,0)
,(0,0)-(0,1)
,(1,1)-(2,1)
, 如果是所有线段都刚刚垂线段那么显然选点(1,1)
,然而选点0,0
可以得到更好的线段长度总和,说明(1,1)
不是最优点
- 一个办法是 坐标乘10 ,然后枚举
O(1000*1000*150)
- 一个算法是模拟退火!!!
- 精度逼近法,如果 一个区域的 最大距离 小于 另一个区域的最小距离,那么显然抛弃另一个,对这个区域可以进行再划分,至于怎么划分 还没具体方法
- 二维三分,求助!证明 在x和y方向 ,距离值函数都是凹函数(上凸)
基于未证明的 凸 假设 下的简化模拟退火, AC
#include <bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) using namespace std; const string filename = "fence3"; void usefile(){ freopen((filename+".in").c_str(),"r",stdin); freopen((filename+".out").c_str(),"w",stdout); } double absarrow(double derx,double dery){ return sqrt(derx*derx+dery*dery); } struct re{ int x1,y1,x2,y2; }l[160]; double dis(double x,double y,int idx){ if(l[idx].x1==l[idx].x2){ if(y<l[idx].y1)return absarrow(x-l[idx].x1,y-l[idx].y1); if(y>l[idx].y2)return absarrow(x-l[idx].x2,y-l[idx].y2); return fabs(x-l[idx].x1); }else{ if(x<l[idx].x1)return absarrow(x-l[idx].x1,y-l[idx].y1); if(x>l[idx].x2)return absarrow(x-l[idx].x2,y-l[idx].y2); return fabs(y-l[idx].y1); } } int main(){ usefile(); srand(size_t(time(NULL))); int n=0; cin >> n; double x=rand()%100; double y=rand()%100; double step=100; tuple<double,double,double>ans; rep(i,0,n){ scanf("%d %d %d %d", &l[i].x1,&l[i].y1,&l[i].x2,&l[i].y2); // 因为平行于坐标轴 所以 必定有一组相等,所以只用换一组 if(l[i].x1>l[i].x2)swap(l[i].x1,l[i].x2); if(l[i].y1>l[i].y2)swap(l[i].y1,l[i].y2); get<2>(ans) += dis(x,y,i); } int d=31; while(step>10e-3){ rep(i,0,500){ // 以任意方向 长度为step进行下降 d((x,y),(newx,newy)) = step double newx,newy; newx=step*(double(rand())/double(RAND_MAX))*(2*(rand()%2)-1); // [-step,step] newy=sqrt(step*step-newx*newx)*(2*(rand()%2)-1)+y; // 保证x y变化的向量长度是 step newx+=x; double lencnt=0; rep(idx,0,n){ lencnt+=dis(newx,newy,idx); } // 如果更优下降 if(lencnt-get<2>(ans)<0){ x=newx; y=newy; ans={newx,newy,lencnt}; } } d++; // 约从 1.1568910657987959 速率开始 step/=log10(d)/log10(20); } printf("%.1lf %.1lf %.1lf\n",get<0>(ans),get<1>(ans),get<2>(ans)); return 0; }
延伸思考, 1.如何证明凸性质,2.如果增加线段,加一些不平行于坐标轴的线段,是否还是有凸的性质
Wisconsin Squares
题目大意
考英语了 考英语了 Guernseys (A), Jerseys (B), Herefords (C), Black Angus (D), and Longhorns (E).
4*4
的矩阵
原来有3*A0,3*B0,4*C0,3*D0,3*E0
现在需要有3*A1,3*B1,3*C1,4*D1,3*E1
现在的操作是 每次替换一个某种0
为 任意一种1
,直到把4*4
的所有替换完
限制,每次操作后,保证 没有相邻(8向)的相同字母, 如C0
和C0
算相同字母, A1
和A0
算相同字母
输入 初始 布局
输出 字典序最小的可行的方案过程和 可行的方案过程的总数
题解
一看就想暴搜啊
......然后 真的就过了,只有一个测试点
#include <bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) using namespace std; const string filename = "wissqu"; pair<int,int> v[10][10]; char s[10][10]; void usefile(){ freopen((filename+".in").c_str(),"r",stdin); freopen((filename+".out").c_str(),"w",stdout); } int cnt[10]; bool success = false; int anscnt = 0; tuple<char,int,int> pick[100]; int di[]={-1,-1,-1,0,0,0,1,1,1}; int dj[]={-1,0,1,-1,0,1,-1,0,1}; void dfs(int deep){ if(deep == 16){ anscnt++; if(!success){ success = true; rep(i,0,16){ printf("%c %d %d\n",get<0>(pick[i]),get<1>(pick[i]),get<2>(pick[i])); } } return ; } rep(k,0,5){ if(deep == 0 && k != 3)continue; if(!cnt[k])continue; rep(i,0,4){ rep(j,0,4){ if(v[i][j].second)continue; bool conflict = false; rep(m,0,9){ int newi = i+di[m]; int newj = j+dj[m]; if(newi < 0 || newj < 0 || newi > 4 || newj > 4){ continue; } if(v[newi][newj].first == k){ conflict = true; break; } } if(conflict)continue; auto old = v[i][j]; v[i][j] = {k,1}; pick[deep] = {'A'+k,i+1,j+1}; cnt[k]--; dfs(deep+1); cnt[k]++; v[i][j] = old; } } } } int main(){ usefile(); rep(i,0,4){ scanf("%s",s[i]); } cnt[0] = 3; cnt[1] = 3; cnt[2] = 3; cnt[3] = 4; cnt[4] = 3; rep(i,0,4){ rep(j,0,4){ v[i][j] = {s[i][j]-'A',0}; } } dfs(0); printf("%d\n",anscnt); return 0; }
总结
我发现 普通的题,基本是一眼算法+分析复杂度+实现
而这种搜索剪枝的是,先上暴搜,逐个尝试加剪枝看效果XD,因为只能大概猜剪枝对效率的影响,而无法很直接的估计复杂度
另外,具体实现的常数有时很重要
和上一章的各种剪枝相比,这一章真的easy
本文其它博客地址
github:https://yexiaorain.github.io/Blog/2019-07-03-USACO-6.4/