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/
恒生电子公司氛围 52人发布
