NOJ刷题总结
+++
HDU2553
可能因为样例过多的缘故，刚开始疯狂TLE,后来就需要打表过。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
char g[N][N];
bool bias1[N], bias2[N], col[N];
int sum;
int storage[10];//打表
void dfs(int u, int n)
{
if(u == n)
{
sum++;
return;
}
for(int i = 0; i < n; i++ )
if(!col[i] && !bias1[u + i] & !bias2[n - u + i])
{
col[i] = bias1[u + i] = bias2[n - u + i] = true;
dfs(u + 1, n);
col[i] = bias1[u + i] = bias2[n - u + i] = false;
}
}
int main()
{
for(int i = 0; i < 10; i++ )
{
sum = 0;
dfs(0, i + 1);
storage[i] = sum;
}
int u;
while(cin >> u, u)
cout << storage[u - 1] << endl;
return 0;
}
NOJ1049 飞机航班求最短路
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25;
int n, m, v;
int h[N], e[N], ne[N], q[N], d[N], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs()
{
int hh = 0, tt = 0;
q[0] = v;
memset(d, -1, sizeof d);
d[v] = 0;
while(hh <= tt)
{
int t = q[hh++];
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(d[j] == -1)
{
d[j] = d[t] + 1;
q[++tt] = j;
}
}
}
for(int i = 0; i < n; i++ )
{
if(i == v) continue;
cout << d[i] << endl;
}
}
int main()
{
cin >> n >> m >> v;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i++ )
{
int x, y;
cin >> x >> y;
add(x, y);
}
bfs();
return 0;
}
NOJ1079 11111...
既然枚举n的倍数复杂度过高，就反过来枚举不同位数的1
#include <cstdio>
int main()
{
int n;
while(~scanf("%I64d", &n))
{
int t = 0, ans = 0;
while(true)
{
t = (10 * t + 1) % n;
ans++;
if(0 == t) break;
}
printf("%d
", ans);
}
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt;
void down(int u)
{
int t = u;
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
swap(h[u], h[t]);
down(t);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
cnt = n;
for (int i = n / 2; i; i -- ) down(i);
while (m -- )
{
printf("%d ", h[1]);
h[1] = h[cnt -- ];
down(1);
}
puts("");
return 0;
}
HDU2546 饭卡
果然自己做出一道dp题是很开心的一件事，（虽然是和模板01背包几乎一样）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int w[N], m, n, g[N][N];
int main()
{
while(cin >> m, m)
{
for(int i = 1; i <= m; i ++ ) cin >> w[i];
cin >> n;
if(n < 5)
cout << n << endl;
else
{
sort(w + 1, w + m + 1);
for(int i = 1; i < m; i ++ )
for(int j = 0; j <= n - 5; j ++ )
{
g[i][j] = g[i - 1][j];
if(j >= w[i]) g[i][j] = max(g[i][j], g[i - 1][j - w[i]] + w[i]);
}
cout << n - g[m - 1][n - 5] - w[m] << endl;
}
}
return 0;
}
VIJ1360 八数码
记录初次使用哈希表
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
int bfs(string s)
{
queue<string> q;
unordered_map<string, int> d;
q.push(s);
d[s] = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
string end = "123804765";
while(q.size())
{
auto t = q.front();
q.pop();
if(t == end) return d[t];
int distence = d[t];
int k = t.find('0');
int x = k / 3, y = k % 3;
for(int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a < 3 && b >= 0 && b < 3)
{
swap(t[a * 3 + b], t[k]);
if(!d.count(t))
{
d[t] = distence + 1;
q.push(t);
}
swap(t[k], t[a * 3 + b]);
}
}
}
}
int main()
{
string s;
cin >> s;
cout << bfs(s) << endl;
return 0;
}
HDU2036 给点坐标求面积
多边形的面积可以转换为若干个三角形面积的相加，三角形顶点是最后一个点
三角形的有向面积计算公式：
s = (x2y3+x3y1+x1y2-x2y1-x3y2-x1y3)/2.0
#include <iostream>
using namespace std;
int n,x1,y1,x2,y2,x3,y3;
double s;
double getArea(int x1,int y1,int x2,int y2,int x3,int y3)
{
return (x2*y3+x3*y1+x1*y2-x2*y1-x3*y2-x1*y3)/2.0;
}
int main(){
while(~scanf("%d",&n))
{
if(!n)break;
s = 0;
scanf("%d %d %d %d %d %d",&x1,&y1,&x2,&y2,&x3,&y3);
s += getArea(x1,y1,x2,y2,x3,y3);
n = n-3;
while(n>0){
n--;
x2 = x3;
y2 = y3;
scanf("%d%d",&x3,&y3);
s += getArea(x1,y1,x2,y2,x3,y3);
}
printf("%.1f
",s);
}
return 0;
}
HDU2048 神，上帝与老天爷 (典型错排dp)
1.假设n个人，前n - 1 个人满足错排，那么第n个人与前面任意一个人互换就可以，一共有(n - 1) * f(n - 1)种情况。
2.假设n个人，前n - 1不满足错排，然后第n个人与其中一个人互换后满足错排。也就是说前n - 2个人满足错排，因为每个人都可以是之前不满足错排的原因，所以这种情况一共有(n - 1) * f(n - 2)种。
综上列出状态转移方程f(n) = (n - 1) * (f(n - 1) + f(n - 2))
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
double num[N], sum[N];
void chart()
{
num[1] = 0, num[2] = 1;
sum[1] = 1, sum[2] = 2;
for(int i = 3; i < 25; i ++ )
{
num[i] = (i - 1) * (num[i - 1] + num[i - 2]), sum[i] = sum[i - 1] * i;
}
}
int main()
{
int t;
cin >> t;
chart();
while(t--)
{
int n;
cin >> n;
printf("%.2lf%%
", (num[n] / sum[n]) * 100.0);
}
return 0;
}
HDU2049 错排
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
int main()
{
int n, m, c;
LL sum[21], f[21];
sum[0] = 1, sum[1] = 1;
f[0] = 1, f[1] = 0;
for(int i = 2; i < 21;i ++ )
{
sum[i] = sum[i-1] * i;
f[i] = (i-1)*(f[i-1] + f[i-2]);
}
cin>>c;
for(int j = 0; j < c;j ++ )
{
cin>>n >> m;
cout << f[m] * (sum[n] / sum[m] /sum[n-m]) << endl;
}
return 0;
}
HDU2045 简单递推
数据n = 3比较卡，要单独赋值。
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 55;
LL dp[N];
void chart()
{
dp[1] = 3, dp[2] = 6, dp[3] = 6;
for(int i = 4; i <= 50; i ++ )
dp[i] = dp[i - 1] + 2 * dp[i - 2];
}
int main()
{
chart();
int n;
while(cin >> n)
cout << dp[n] << endl;
return 0;
}