1001:King's Cake（数论）
http://acm.hdu.edu.cn/showproblem.php?pid=5640
这题有点辗转相除的意思。基本没有什么坑点。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#define LL long long using namespace std; int n, m; int main()
{
//freopen("test.in", "r", stdin);
int T;
scanf("%d", &T);
for (int times = ; times <= T; ++times)
{
scanf("%d%d", &n, &m);
int ans = ;
while (n&&m)
{
if (n > m) swap(n, m);
ans += m/n;
m = m%n;
}
printf("%d\n", ans);
}
return ;
}
1002:King's Phone（模拟）
http://acm.hdu.edu.cn/showproblem.php?pid=5641
这题坑点有点多，3A。。首先任意一条连线，需要判断中间有没有经过什么点。
然后不能有重复的点，需要判断。
其次，对于0和大于9的数据需要判断掉。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#define LL long long using namespace std; int k, s[];
bool vis[]; int cross(int from, int to)
{
if (from > to) swap(from, to);
if (from == && to == ) return ;
if (from == && to == ) return ;
if (from == && to == ) return ;
if (from == && to == ) return ;
if (from == && to == ) return ;
if (from == && to == ) return ;
if (from == && to == ) return ;
if (from == && to == ) return ;
return ;
} bool work()
{
if (k < ) return false;
memset(vis, false, sizeof(vis));
int t;
for (int i = ; i < k; ++i)
{
if (s[i-] == || s[i] == ) return false;
if (s[i-] > || s[i] > ) return false;
if (s[i] == s[i-]) return false;
if (vis[s[i]]) return false;
t = cross(s[i-], s[i]);
if (t && !vis[t]) return false;
vis[s[i-]] = true;
vis[s[i]] = true;
}
return true;
} int main()
{
//freopen("test.in", "r", stdin);
int T;
scanf("%d", &T);
for (int times = ; times <= T; ++times)
{
scanf("%d", &k);
for (int i = ; i < k; ++i)
scanf("%d", &s[i]);
if (work()) printf("valid\n");
else printf("invalid\n");
}
return ;
}
1003:King's Order（递推）
http://acm.hdu.edu.cn/showproblem.php?pid=5642
这题是个递推，但是没考虑清楚，递推式一直是错的，4A。。
设p[n][k]表示n长度字符串，结尾k个相同的情况数。
那么：
p[i][1] = 25*(p[i-1][1]+p[i-1][2]+p[i-1][3])%MOD;
p[i][2] = p[i-1][1];
p[i][3] = p[i-1][2];
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#define LL long long
#define MOD 1000000007 using namespace std; const int maxN = ;
int n;
LL p[maxN][]; void init()
{
p[][] = ;
p[][] = ;
p[][] = ;
for (int i = ; i < maxN; ++i)
{
p[i][] = *(p[i-][]+p[i-][]+p[i-][])%MOD;
p[i][] = p[i-][];
p[i][] = p[i-][];
}
} int main()
{
//freopen("test.in", "r", stdin);
init();
int T;
scanf("%d", &T);
for (int times = ; times <= T; ++times)
{
scanf("%d", &n);
cout << (p[n][]+p[n][]+p[n][])%MOD << endl;
}
return ;
}
1004:King's Game（递推）
http://acm.hdu.edu.cn/showproblem.php?pid=5643
这一题想法类似于O(n)做法的约瑟夫问题。需要考虑子问题，然后映射回来。具体的方法百度百科里有。
最后
p(n, k) = (p(n-1, k+1)+k)%n or n(if 0)
不过我二逼的离线了一发，然后MLE了。。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#define LL long long using namespace std; const int maxN = ;
/*
int p[maxN][maxN]; void init()
{
for (int i = 0; i < maxN; ++i)
p[1][i] = 1;
for (int i = 2; i < maxN; ++i)
{
for (int j = 1; j < maxN; ++j)
{
p[i][j] = (p[i-1][j+1]+j)%i;
if (!p[i][j]) p[i][j] = i;
}
}
}
*/ int dfs(int n, int k)
{
if (n == ) return ;
int ans;
ans = (dfs(n-, k+)+k)%n;
if (!ans) ans = n;
return ans;
} int main()
{
//freopen("test.in", "r", stdin);
//init();
int n, T;
scanf("%d", &T);
for (int times = ; times <= T; ++times)
{
scanf("%d", &n);
printf("%d\n",dfs(n, ));
}
return ;
}
1005:没有想法。。应该是水平还没到火候。。。