USACO1.4 题解
Arithmetic Progressions
题意
让你求长为n的由小于2*m*m的双平方数组成的等差数列有几个
双平方数：形如 B=P*P+Q*Q,p,q>0的数
题解
枚举首项和公差，判n个数是否为等差数列，复杂度为m^4
m*m/(n-1)为公差的枚举次数，m*m为首项的结局次数，n为数列的枚举次数，其中还可以剪枝一下，如果数列的最后一项大于2*m*m,就break；
另一个优化是枚举前两个双平方数，算出首项公差，双平方的数量级是2e4,
代码
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <set>
#include<algorithm>
#include<map>
typedef long long ll;
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define per(i,j,k) for(int i = (int)j;i >= (int)k;i --)
#define md(x) x=(x+mod)%mod
#define pb push_back
#define pii pair<int,int>
#define x first
#define y second
int smain();
#define ONLINE_JUDGE
int main() {
//ios::sync_with_stdio(false);
#ifdef ONLINE_JUDGE
FILE *myfile;
myfile = freopen("ariprog.in", "r", stdin);
if (myfile == NULL)
fprintf(stdout, "error on input freopen\n");
FILE *outfile;
outfile = freopen("ariprog.out", "w", stdout);
if (outfile == NULL)
fprintf(stdout, "error on output freopen\n");
#endif
smain();
return 0;
}
const int maxn = 13;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
int n;
int m;
int cnt[130000];
vector<pii> ans;
vector<int> V;
int smain() {
FAST_IO;
cin >> n>>m;
rep(i, 0, m)rep(j, 0, m) {
cnt[i*i + j * j]++;
}
int mm = m * m * 2;
rep(i, 0, mm)if (cnt[i])V.push_back(i);
int a, b;
sort(V.begin(), V.end());
rep(i, 0, V.size() - n+1) {
rep(j, i+1, V.size() - n+1) {
a = V[i]; b = V[j] - V[i];
if (a + (n - 1)*b > mm)continue;
//if (b <= 0)continue;
int ok = 1;
per(k,n-2,1) {
int ai = V[j] + b * k;
if (ai > mm) { ok = 0; break; }
if(cnt[ai] == 0) { ok = 0; break; }
}
if (ok)ans.push_back({ b,a });
}
}
sort(ans.begin(), ans.end());
if(ans.empty())cout<<"NONE"<<endl;
for (auto t : ans) {
cout << t.y <<' '<< t.x << endl;
}
cin >> n;
return 0;
}
心路历程
QAQ
Mother's Milk
题意
三个杯子的容量为a,b,c，每次选一个杯子X倒到另一个杯子Y里，直到Y倒不下或X倒空。问杯子c在杯子a为空的情况下水体积的所有可能的取值？
题解
状态只有20^3个，爆搜即可。
dfs的具体写法就是写六个状态转移，用123的全排列可以简化代码。
倒水的过程我封装了一下。
代码
int n;
int m;
int a, b, c;
set<int> ans;
bool pour(int& x, int& y,int aa,int bb) {
if (x==0||y == bb)return 0;
if (x + y <= bb)y = x + y,x=0;
else x = x + y - bb, y = bb;
return 1;
}
void dfs(int x, int y, int z) {
if (ans.count(x * 10000 + y * 100 + z))return;
ans.insert(x * 10000 + y * 100 + z);
int tx = x, ty = y, tz = z;
if (pour(x, y, a, b))dfs(x, y, z); x = tx, y = ty;
if (pour(y, x, b, a))dfs(x, y, z); x = tx, y = ty;
if (pour(x, z, a, c))dfs(x, y, z); x = tx, z = tz;
if (pour(z, x, c, a))dfs(x, y, z); x = tx, z = tz;
if (pour(y, z, b, c))dfs(x, y, z); y = ty, z = tz;
if (pour(z, y, c, b))dfs(x, y, z); y = ty, z = tz;
}
int main() {
FAST_IO;
cin >>a>>b>>c;
int i = 1;
int last = -1;
dfs(0, 0, c);
set<int> out;
for (auto t : ans)if(t/10000==0)out.insert(t%100);
for (auto t : out)cout << t << ' ';
cout << endl;
cin >> n;
}
心路历程
一开始以为有什么技巧，想着用迭代加深来判dfs结束条件，结果想歪了。
其实所有状态搜完，dfs就结束了。
Prime Palindromes
题意
问区间(a,b)有哪些质数是回文数。
题解
判断一个1e8的质数，直接暴力即可。
如何生成回文数？我用了一个数组，用dfs生成前一半，然后在dfs底层对称一下，算出它对应的数。
数组可以用string代替，这样就可以reverse生成对称串了（其实数组也可以用reverse，不过string可以拼接）。
还有直接生成数字的递归写法。
代码
#include<algorithm>
#include<iostream>
#include<sstream>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<math.h>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string>
#include<ctime>
#include<stack>
#include<map>
#include<set>
#include<list>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define REP(i,j,k) for(int i = (int)j;i < (int)k;i ++)
#define per(i,j,k) for(int i = (int)j;i >= (int)k;i --)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define MD(x) x%=mod
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
//#define pii pair<int,int>
//#define x first
//#define y second
typedef double db;
typedef long long ll;
const int MAXN = 1e6;;
const int maxn = 1e3 + 5;
const int INF = 1e9;
const db eps = 1e-7;
const int mod = 1e9 + 7;
int n;
int N;
//int ans;
int num[10];
int isp[10005];
set<int> ans;
int a, b;
void sieveP() {
rep(i, 1, 10000) {
int ok = 1;
for (int j = 2; j*j <= i; j++) {
if (i%j == 0)ok = 0;
}
if (ok)isp[i] = 1;
}
}
bool isprime(int x) {
int ok = 1;
for (int i = 2; i*i <= x;i++)if (isp[i]) {
if (x%i == 0)ok = 0;
}
return ok;
}
void gene(int n) {
if (n == 0) {
if (N % 2) { rep(i, 0, 9) { num[N / 2 + 1] = i; gene(n - 1); } }
else {
rep(i, N / 2 + 1, N)num[i] = num[N + 1 - i];
int val = 0;
rep(i, 1, N)val*= 10, val += num[i];
// cout << val << endl;
if (val<=1e8&&isprime(val)&&val>=a&&val<=b)ans.insert(val);
return;
}
}
else if (n == -1) {
rep(i, N / 2 + 2, N)num[i] = num[N + 1 - i];
int val=0;
rep(i, 1, N)val *= 10, val += num[i];
//cout << val << endl;
if (isprime(val) && val >= a && val <= b)ans.insert(val);
return;
}
else rep(i, 0, 9) { num[n] = i; gene(n - 1); }
}
int main() {
FAST_IO;
sieveP();
cin >> a >> b;
int bita = 0;
int bitb = 0,aa=a,bb=b;
while (aa) { bita++; aa /= 10; }
while (bb) { bitb++; bb /= 10; }
for (N = bita; N <= bitb; N++) {
gene(N / 2);
}
for (auto t : ans)cout << t << endl;
cin >> n;
return 0;
}
/*
5 100000000
*/
以下是三个标程：
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
FILE *fout;
long a, b;
int
isprime(long n)
{
long i;
if(n == 2)
return 1;
if(n%2 == 0)
return 0;
for(i=3; i*i <= n; i+=2)
if(n%i == 0)
return 0;
return 1;
}
void
gen(int i, int isodd)
{
char buf[30];
char *p, *q;
long n;
sprintf(buf, "%d", i);
p = buf+strlen(buf);
q = p - isodd;
while(q > buf)
*p++ = *--q;
*p = '\0';
n = atol(buf);
if(a <= n && n <= b && isprime(n))
fprintf(fout, "%ld\n", n);
}
void
genoddeven(int lo, int hi)
{
int i;
for(i=lo; i<=hi; i++)
gen(i, 1);
for(i=lo; i<=hi; i++)
gen(i, 0);
}
void
generate(void)
{
genoddeven(1, 9);
genoddeven(10, 99);
genoddeven(100, 999);
genoddeven(1000, 9999);
}
void
main(void)
{
FILE *fin;
fin = fopen("pprime.in", "r");
fout = fopen("pprime.out", "w");
assert(fin != NULL && fout != NULL);
fscanf(fin, "%ld %ld", &a, &b);
generate();
exit (0);
}
//注意到偶数回文串必被11整除，所以生成奇数的即可
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
int primelist[100000];
int nprimes;
int isPrime(int num);
int reverse2(int i, int j);
int compare(const void *p, const void *q) { return *(int *)p-*(int *)q; }
void main (void) {
ifstream infile("pprime.in");
ofstream outfile("pprime.out");
int i, j, begin, end, num;
infile>>begin>>end;
if (begin <= 11 && 11 <=end)
primelist[nprimes++] = 11;
for (j = 0; j <= 999; j++)
for (i = 0; i <= 9; i++) {
num = reverse2(j,i);
if (num >= begin && num <=end && isPrime(num))
primelist[nprimes++] = num;
}
qsort(primelist, nprimes, sizeof(int), compare);
for (i = 0; i < nprimes; i++)
outfile << primelist[i] << "\n";
}
int
reverse2(int num, int middle) {
int i, save=num, digit, combino = 1;
for (i = 0; num; num /= 10) {
digit = num % 10;
i = 10 * i + digit;
combino *= 10;
}
return i+10*combino*save+combino*middle;
}
int isPrime(int num) {
int i;
if (num <= 3) return 1;
if (num%2 == 0 || num%3 ==0) return 0;
for (i = 5; i*i <= num; i++)
if (num %i ==0)
return 0;
return 1;
}
//递归不用数组
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
FILE *f;
int a, b;
int isPrime(int num);
void genPalind(int num, int add, int mulleft, int mulright);
void tryPalind(int num);
int main(){
int i;
char first;
f=fopen("pprime.in", "r");
fscanf(f, "%d%d", &a, &b);
fclose(f);
f=fopen("pprime.out", "w");
if (a<=5)
fprintf(f, "%i\n", 5);
if (a<=7 && b>=7)
fprintf(f, "%i\n", 7);
if (a<=11 && b>=11)
fprintf(f, "%i\n", 11);
genPalind(3, 0, 100, 1);
genPalind(5, 0, 10000, 1);
genPalind(7, 0, 1000000, 1);
fclose(f);
}
void tryPalind(int num){
if (!(num&1))
return;
if (num<a || num>b)
return;
if (!(num%3) || !(num%5) || !(num%7))
return;
if (!isPrime(num))
return;
fprintf(f, "%d\n", num);
}
void genPalind(int num, int add, int mulleft, int mulright){
int i, nmulleft, nmulright;
if (num==2){
for (i=0; i<10; i++)
tryPalind(add+mulleft*i+mulright*i);
}
else if (num==1){
for (i=0; i<10; i++)
tryPalind(add+mulright*i);
}
else {
nmulleft=mulleft/10;
nmulright=mulright*10;
num-=2;
for (i=0; i<10; i++)
genPalind(num, add+i*mulleft+i*mulright, nmulleft, nmulright);
}
}
int isPrime(int num){
int koren, i;
koren=(int)sqrt(1.0*num);
for (i=11; i<=koren; i+=2)
if (!(num%i))
return 0;
return 1;
}
心路历程
一开始打算写最后的那个标程，不会啊QAQ orz%%%
Superprime Rib
题意
输出所有n位的super prime.
super prime: 如果质数X，有X/10，X/100，X/1000...都是质数，那么它就是sprime
题解
上一题简化版，直接从第一个数字不断往后dfs，每层都是质数，所以剪枝性很强。
代码
//头文件省略
int n;
int N;
//int ans;
int num[10];
int isp[10005];
set<int> ans;
int a, b;
void sieveP() {
rep(i, 1, 10000) {
int ok = 1;
for (int j = 2; j*j <= i; j++) {
if (i%j == 0)ok = 0;
}
if (ok)isp[i] = 1;
}
}
bool isprime(int x) {
if(x==1)return 0;
int ok = 1;
for (int i = 2; i*i <= x;i++)if (isp[i]) {
if (x%i == 0)ok = 0;
}
return ok;
}
void gene(int n,int num) {
if (n == 0) { if(num/N)cout << num<<endl; return; }
rep(i, 0, 9) {
if (isprime(num * 10 + i))gene(n - 1, num * 10 + i);
}
}
int smain() {
FAST_IO;
sieveP();
cin >> n;
N = pow(10, n - 1);
gene(n,0);
cin >> n;
return 0;
}
心路历程
水