高斯日记
正确答案:
1799-7-16
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int months[13] = {
0,31,0,31,30,31,30,31,31,30,31,30,31};
bool check(int x)
{
if((x%4 == 0 && x%100) || x%400 == 0) return true;
return false;
}
int main()
{
int tot = 8113, cnt = 0;
int year = 1777, m = 4, d = 30;
while(cnt != tot)
{
if(check(year)) months[2] = 29;
else months[2] = 28;
for(int i = m; i <= 12; i++,m++)
{
for(int j = d; j <= months[i]; j++,d++)
{
cnt++;
if(j== months[i]) d = 0;
if(cnt == tot) break;
}
if(i == 12) m = 0;
if(cnt == tot) break;
}
if(cnt != tot) year++;
}
printf("%d-%d-%d\n",year,m,d);
return 0;
}
排它平方数
正确答案:
639172
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
set<int> work(ll x)
{
set<int>c;
while(x)
{
c.insert(x%10);
x /= 10;
}
return c;
}
int main()
{
set<int> a, b;
vector<int>v;
for(int i =100000; i <= 999999; i++)
{
a.clear(); b.clear();
int t = i;
a = work(t);
if(a.size() != 6) continue;
ll ans = i;
ans = ans*ans;
b = work(ans);
int ok = 1;
for(set<int>::iterator it = b.begin(); it != b.end(); it++)
if(a.find(*it) != a.end()) ok = 0;
if(ok) v.push_back(i);
}
for(auto s : v) cout<<s<<'\n';
return 0;
}
振兴中华
正确答案:
35
#include <algorithm>
using namespace std;
typedef long long ll;
int dp[6][6];
int main()
{
dp[1][1] = 1;
for(int i = 1; i <= 4; i++)
for(int j = 1; j <= 5; j++)
dp[i][j] += dp[i-1][j]+dp[i][j-1];
cout<<dp[4][5]<<endl;
return 0;
}
颠倒的价值
正确答案:
9088
#include <iostream>
#include <cstdio>
#include <string>
#include <set>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
unordered_map<int,int>mp;
struct node{
int ago, now;
};
void init()
{
for(int i = 0; i < 10; i++)
{
if(i == 6) mp[6] = 9;
else if(i == 9) mp[9] = 6;
else mp[i] = i;
}
}
int main()
{
init();
vector<node> a, b;
for(int i = 1000; i <= 9999; i++)
{
int t = i;
string temp = "";
while(t)
{
temp += (char)(mp[t%10] + '0');
t /= 10;
}
if(temp[0] == '0') continue;
int y = stoi(temp);
if(i - y > 200 && i - y < 300) a.push_back({
i,y-i});
if(y - i > 800) b.push_back({
i,y-i});
}
int answer;
for(auto x : a)
for(auto y : b)
if(x.now + y.now == 558)
answer = x.ago;
cout<<answer<<'\n';
return 0;
}
前缀判断
正确答案：
*(haystack++) != *(needle++)
#include <iostream>
#include <cstdio>
#include <string>
#include <set>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
char*prefix(char * haystack_start, char *needle_star) //母串 子串
{
char* haystack = haystack_start;
char* needle = needle_star;
while(*haystack && *needle) //两个指针都没有越界
{
//移动指针并判断
if(*(haystack++) != *(needle++)) return NULL;
}
if(*needle) return NULL;
return haystack_start;
}
int main()
{
cout<<prefix("abcd123","abc")<<endl;
cout<<prefix("abcd123","abd")<<endl;
return 0;
}
逆波兰表达式
正确答案：
evaluate(x + 1 + v1.n)
#include <iostream>
#include <cstdio>
#include <string>
#include <set>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
struct EV
{
int result; //计算结果
int n; //消耗掉的字符数
};
struct EV evaluate(char* x)
{
struct EV ev = {
0, 0};
struct EV v1;
struct EV v2;
if(*x == 0) return ev;
if(x[0] >= '0' && x[0] <= '9')
{
ev.result = x[0] - '0';
ev.n = 1;
return ev;
}
v1 = evaluate(x + 1); //递归
v2 = evaluate(x + 1 + v1.n); //填空位置
if(x[0] == '+') ev.result = v1.result + v2.result;
if(x[0] == '*') ev.result = v1.result * v2.result;
if(x[0] == '-') ev.result = v1.result - v2.result;
ev.n = 1 + v1.n + v2.n;
return ev;
};
int main()
{
string s = "-+3*5+261";
EV x = evaluate((char*)(s.c_str()));
cout<<x.result<<endl;
return 0;
}
编程题
错误票据
题目链接
题目大意
某涉密单位下发了某种票据，并要在年终全部收回。
每张票据有唯一的 I D ID ID 号。全年所有票据的 I D ID ID 号是连续的，但 I D ID ID 的开始数码是随机选定的。
因为工作人员疏忽，在录入 I D ID ID 号的时候发生了一处错误，造成了某个 I D ID ID 断号，另外一个 I D ID ID 重号。
你的任务是通过编程，找出断号的 I D ID ID 和重号的 I D ID ID。
假设断号不可能发生在最大和最小号。
输入格式
要求程序首先输入一个整数 N N N ( N N N < 100)表示后面数据行数。
接着读入 N N N 行数据。
每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000），请注意行内和行末可能有多余的空格，你的程序需要能处理这些空格。
每个整数代表一个 I D ID ID 号。
输出格式
要求程序输出1行，含两个整数 m m m n n n，用空格分隔。
其中， m m m 表示断号 I D ID ID， n n n 表示重号 I D ID ID
输入样例
2
5 6 8 11 9
10 12 9
输出样例
7 9
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 的算法
将所有数据存入一个数组，可以用静态数组，也可以用动态数组，然后快速排序一下所有数据，从小到大往后遍历没有出现的数就是断号，重复出现的数就是重号。
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<int> v;
int main()
{
int cnt;
cin >> cnt;
string line;
getline(cin, line);
while (cnt -- )
{
int t;
getline(cin, line);
stringstream ssin(line);
while (ssin >> t) v.push_back(t);
}
sort(v.begin(),v.end());
int res1, res2;
for (int i = 1; i < v.size(); i++)
if (v[i] == v[i - 1]) res2 = v[i];
else if (v[i] >= v[i - 1] + 2) res1 = v[i] - 1;
cout << res1 << ' ' << res2 << endl;
return 0;
}
时间复杂度 O ( n ) O(n) O(n) 的算法
用 s e t set set 存储数据。
买不到的数目
题目链接
题目大意
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入格式
两个正整数，表示每种包装中糖的颗数(都不多于1000)
输出格式
一个正整数，表示最大不能买到的糖数
输入样例
4 7
输出样例
17
a x + b y = C ax + by = C ax+by=C,不定方程的解 x x x = 4, y y y = 7, C C C = 17 这种情况下， a b ab ab 实际上有解，72 + （7 - 4） == 37 - 1*4
x , y x,y x,y互质，一定有解且解的数目无穷
C C C 是 g c d ( x , y ) gcd(x,y) gcd(x,y) 的倍数，方程一定有解，而且有无穷多解
条件：一定有解 => x , y x,y x,y 互质
#include <cstdio>
using namespace std;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
printf("%d\n",(n-1)*(m-1)-1);
return 0;
}
剪格子
题目链接
题目大意
如下图所示，3 x 3 的格子中填写了一些整数。
±-–±-+
|10 1|52|
±-***–+
|20|30 1|
*******–+
| 1| 2| 3|
±-±-±-+
我们沿着图中的星号线剪开，得到两个部分，每个部分的数字和都是60。
本题的要求就是请你编程判定：对给定的 m x n m x n mxn 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 0。
输入格式
程序先读入两个整数 m m m n n n 用空格分割 ( m , n m,n m,n < 10)。
表示表格的宽度和高度。
接下来是 n n n 行，每行 m m m个 正整数，用空格分开。每个整数不大于10000。
输出格式
输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目
输入样例
3 3
10 1 52
20 30 1
1 2 3
输出样例
3
1.判断只有两个连通块
2.只搜了一笔画的连通块
3.包含两笔
从起点开始 dfs s = {（0,0）}
dfs(s) < if(两部份的和相等)
for(x,y) in s
for(x-1,y)(x+1,y),(x,y-1)(x,y+1)
新点 -> s
dfs(s)
// s 中删除起点
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#define pb push_back
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int maxn = 15, base = 131, inf = 0x3f3f3f3f;
int n, m;
int a[maxn][maxn];
bool st[maxn][maxn];
int sum, res = inf;
PII cands[maxn*maxn];
int fa[maxn*maxn];
set<ULL> hash_table;
int dir[4][2] = {
-1, 0, 0, 1, 1, 0, 0, -1}; //方向
int find(int x) //路径压缩
{
if(fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
bool inbound(int x, int l, int r) //判断位置是否合法
{
if(x < l || x >= r) return false; //不合法
return true;
}
bool check_connect(int k) //检查剩余的是否连通
{
for(int i = 0; i < n*m; i++) fa[i] = i;
int cnt = n*m - k;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(!st[i][j])
{
for(int k = 0; k < 4; k++)
{
int tx = i + dir[k][0], ty = j + dir[k][1];
if(!inbound(tx, 0, n) || !inbound(ty, 0, m)) continue;
if(st[tx][ty]) continue;
int p1 = find(i*m + j), p2 = find(tx*m + ty);
if(p1 != p2)
{
fa[p1] = p2;
cnt--;
}
}
}
if(cnt != 1) return false;
return true;
}
bool check_exists(int k)
{
static PII bk[maxn*maxn];
for(int i = 0; i < k; i++) bk[i] = cands[i];
sort(bk, bk + k);
ULL x = 0;
for(int i = 0; i < k; i++)
{
x = x*base + bk[i].first + 1;
x = x*base + bk[i].second + 1;
}
if(hash_table.count(x)) return true;
hash_table.insert(x);
return false;
}
void dfs(int s, int k)
{
if(s == sum/2)
{
if(check_connect(k)) res = min(res,k);
return;
}
vector<PII> points;
for(int i = 0; i < k; i++)
{
int x = cands[i].first, y = cands[i].second;
for(int j = 0; j < 4; j++)
{
int tx = x + dir[j][0], ty = y + dir[j][1];
if(!inbound(tx,0,n) || !inbound(ty,0,m)) continue;
if(st[tx][ty]) continue;
cands[k] = {
tx, ty};
if(k+ 1 < res && !check_exists(k+1)) points.pb({
tx,ty});
}
}
sort(points.begin(), points.end());
reverse(points.begin(), points.end());
for(int i = 0; i < points.size(); i++)
{
if(!i || points[i] != points[i-1])
{
cands[k] = points[i];
int x = points[i].first, y = points[i].second;
st[x][y] = true;
dfs(s + a[x][y], k + 1);
st[x][y] = false;
}
}
}
int main()
{
scanf("%d%d",&m,&n);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
scanf("%d",&a[i][j]),sum += a[i][j];
if(sum%2 == 0)
{
st[0][0] = true;
cands[0] = {
0, 0};
dfs(a[0][0], 1);
}
if(res == inf) res = 0;
printf("%d\n",res);
return 0;
}
大臣的旅费
题目链接
题目大意
很久以前， T T T 王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费， T T T 国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
J J J 是 T T T 国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。
聪明的 J J J 发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第 x x x 千米到第 x + 1 x+1 x+1 千米这一千米中（ x x x 是整数），他花费的路费是 x + 10 x+10 x+10 这么多。也就是说走 1 千米花费11，走 2 千米要花费 23。
J J J 大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入格式
输入的第一行包含一个整数 n n n，表示包括首都在内的T王国的城市数
城市从 1 开始依次编号，1 号城市为首都。
接下来 n − 1 n-1 n−1 行，描述 T T T 国的高速路（T国的高速路一定是 n − 1 n-1 n−1 条）
每行三个整数 P i , Q i , D i P_i, Q_i, D_i Pi,Qi,Di，表示城市 P i P_i Pi 和城市 Q i Q_i Qi 之间有一条高速路，长度为 D i D_i Di 千米。
输出格式
输出一个整数，表示大臣 J J J 最多花费的路费是多少。
输入样例
5
1 2 2
1 3 1
2 4 5
2 5 4
输出样例
135
求树的直径，两次 D F S DFS DFS 即可。
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 7;
typedef long long ll;
int tot, n;
struct node{
int from, to, w;
int ne;
}edge[maxn<<1];
int head[maxn<<1], dis[maxn<<1];
void add(int x,int y,int w)
{
edge[++tot].to = y;
edge[tot].w = w;
edge[tot].ne = head[x];
head[x] = tot;
}
void dfs(int rt, int fa, int w)
{
dis[rt] = w;
for(int i = head[rt]; i; i = edge[i].ne)
{
int to = edge[i].to;
if(to != fa) dfs(to, rt, w + edge[i].w);
}
}
int main()
{
scanf("%d",&n);
memset(head, -1, sizeof head);
for(int i = 0; i < n - 1; i++)
{
int x, y, z;
scanf(" %d%d%d",&x,&y,&z);
add(x, y, z), add(y, x, z);
}
dfs(1, -1, 0);
int u = 1;
for(int i = 2; i<= n; i++)
if(dis[i] > dis[u]) u = i;
dfs(u, -1, 0);
for(int i = 1; i <= n; i++)
if(dis[i] > dis[u]) u = i;
ll ans = (ll)dis[u]*(dis[u]+21)/2;
printf("%lld\n",ans);
return 0;
}
v e c t o r vector vector 存储
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
struct node{
int to;
ll w;
};
vector<node>v[maxn];
ll dis[maxn];
void dfs(int rt, int fa, ll w) //rt 当前结点 fa 父节点 防止回溯
{
dis[rt] = w;
vector<node>::iterator it;
for(it = v[rt].begin(); it != v[rt].end();it++)
{
node now = *it;
if(now.to != fa) dfs(now.to, rt, now.w + w);
}
}
int Fast(int now, int total) //寻找最远的点
{
for(int i = 1; i <= total; i++)
if(dis[i] > dis[now]) now = i;
return now;
}
int main()
{
int n;
cin>>n;
for(int i = 1; i < n; i++)
{
int x,y; ll z;
cin>>x>>y>>z;
v[x].push_back({
y,z});
v[y].push_back({
x,z});
}
dfs(1, -1, 0);
int rt = Fast(1, n);
dfs(rt, -1, 0);
rt = Fast(rt, n);
cout<<(dis[rt]+21)*dis[rt]/2<<endl;
return 0;
}