电子商务 网站开发,梅县区住房和城乡规划建设局官方网站,专业做招商的公司,百度推广多少钱第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛#xff08;同步赛#xff09;
题目总结
A题 切蛋糕
题目信息 解题思路
如果我们将 1/k展开到二进制的形式#xff0c;那么就可以计算出 需要 多少块1/(2^i) 蛋糕#xff0c;因此就可以创建出分割的方案#xff0c;最后进行…第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛同步赛
题目总结
A题 切蛋糕
题目信息 解题思路
如果我们将 1/k展开到二进制的形式那么就可以计算出 需要 多少块1/(2^i) 蛋糕因此就可以创建出分割的方案最后进行打包。 本题还有一个有趣的地方是知道需要多少块的蛋糕后还需要计算出需要切割多少次 假如说需要 1个四等分的 1个八等分的3个十六等分的4个三十二等分的 那么 十六等分的需要切割次数 ⌈\lceil⌈42\frac{4}{2}24⌉\rceil⌉2可以得到四个三十二等分 八等分需要的切割次数 ⌈\lceil⌈十六等分切割次数十六等分原需要数额2\frac{十六等分切割次数十六等分原需要数额}{2}2十六等分切割次数十六等分原需要数额⌉\rceil⌉ 也就是说计算切割次数需要受到前面切割次数信息的影响。
二进制小数点可以直接使用double进行计算精度是足够的
AC代码
#include bits/stdc.h
using namespace std;typedef long long LL;
const double esp 1e-10;
const int N 20;
LL a[N];
LL k;
bool b[N], flag;
int opt[N];
int cut_opt[N];bool Check(int n)
{static LL l a[10] - k, r a[10] k;double sum 0;for (int i 0; i n; i ){if (!b[i]) continue;if (i 10)sum (a[10 - i]) * k;elsesum k * 1.0 / a[i - 10];}if (n 10) // (a[10 - i]) * k{static int i; i n;if (sum (a[10 - i]) * k l sum (a[10 - i]) * k r){flag true;return true;}else if (sum (a[10 - i]) * k l)return true;return false;}else // 1.0 / a[i - 10];{static int i; i n;if (sum k * 1.0 / a[i - 10] l sum k * 1.0 / a[i - 10] r){flag true;return true;}else if (sum k * 1.0 / a[i - 10] l)return true;return false;}
}int main()
{a[0] 1;for (int i 1; i N; i )a[i] (a[i - 1] 1);memset(b, false, sizeof b);cin k;if (k 1) // 注意{printf(1\n);printf(2 1 0\n);return 0;}flag false;double tmp 1.0 / k;for (int i 1; i 15; i ){if (abs(tmp - 1.0 / a[i]) esp){b[i] true;break;}else if (tmp 1.0 / a[i]){tmp - 1.0 / a[i];b[i] true;}else{b[i] false;}}/*for (int i 0; i 15; i ){printf(i%d, b[%d]%d\n, i, i, b[i]);}
*/for (int i 15; i 1; i -- ){opt[i] b[i] * k;}int outcnt k;memset(cut_opt, 0, sizeof cut_opt);for (int i 14; i 1; i -- ){cut_opt[i - 1] (opt[i] 1) / 2;opt[i - 1] ((opt[i] 1) / 2);outcnt cut_opt[i - 1];}cout outcnt endl;// 需要切割的for (int i 0; i 15; i ){if (cut_opt[i] ! 0){for (int j 1; j cut_opt[i]; j )printf(1 %d\n, i);}}int cnt 0;vectorint pick;// b[i] 打包的for (int i 0; i 15; i )if (b[i]){cnt b[i];pick.push_back(i);}for (int i 1; i k; i ){printf(2 %d, cnt);for (int j 0; j pick.size(); j )printf( %d, pick[j]);putchar(\n);}return 0;
}
小宝的幸运数组
题目信息 解题思路
需要注意子序列如最长上升子序列LIS和子串的区别 这里子数组的定义和子串类似 这里关键是对 原数组的前缀和 对k进行求余得到的余数k记录下来他的位置然后对余数进行分析 余数 0可以直接将下边作为一种解进行更新答案 余数 1, res min(res, max - min); 也就是说最长的min 1 ~ max这一段子序列是可行的而且是余数等于1情况下最长的。 … 余数 k-1 经过分析发现子需要记录下来 余数中最先遇到的 min下标与最后遇到的 max下标即可。
AC代码
#include bits/stdc.h
using namespace std;typedef long long LL;
const int N 100010;
const int INF 0x3f3f3f3f;
int a[N], b[N];
int n, k;
LL q[N], sum[N];int main()
{int T; cin T;while (T -- ){cin n k;sum[0] 0;memset(a, -1, sizeof a);memset(b, -1, sizeof b);int res -1;for (int i 1; i n; i ){scanf(%lld, q[i]);sum[i] (sum[i - 1] q[i]) % k;if (a[sum[i]] -1){a[sum[i]] i;}b[sum[i]] i;if (sum[i] 0){res max(res, i);}else{res max(res, b[sum[i]] - a[sum[i]]);}}/// cout ###########\n;if (res 0) puts(-1);else cout res endl;}return 0;
}
C题上进的凡凡
题目信息 解题思路
关键的思路就是使用dp的思想 以 a[i] 为开始的上进数组个数 f[i] 当 a[i]a[i1] f[i] 1 f[i 1] 否则 f[i] 1 最后累加求和即可
AC代码
#include bits/stdc.h
using namespace std;typedef long long LL;const int N 100010, INF 0x3f3f3f3f;
int a[N], f[N];
int n;int main()
{cin n;for (int i 1; i n; i )scanf(%d, a[i]);LL res 0;a[n 1] -INF;for (int i n; i 1; i -- ){f[i] 1;if (a[i] a[i 1])f[i] f[i 1];res f[i];}cout res endl;return 0;
}
D题Seek the Joker I
原题信息 解题思路
本题是博弈论方向的题目对于此类问题我们需要从 必定失败的局面出发推导出可以让对手达到必定失败的局面-》必胜 以及无法让对手达到必定失败的局面-必败最后找到规律有时间可以证明写出结果即可 AC代码
#include bits/stdc.h
using namespace std;bool Check(int n, int k)
{if (n % (k 1) 0) return false;return true;
}
int main()
{int t; cin t;while (t -- ){static int n, k;scanf(%d%d, n, k);if (Check(n - 1, k)){/// cout win endl;puts(yo xi no forever!);}else{/// cout lose endl;puts(ma la se mi no.1!);}}return 0;
}E Seek the Joker II
原题信息 解题思路
方法与上题目相同但是推导比较易错** 最终的规律可以使用dp的形式表达出来 **
AC代码
#include bits/stdc.h
using namespace std;typedef long long LL;
const int N 3000010;
bool st[N 1000000];
LL a[N 1000000];bool Check(int x, int y)
{if (a[x] -1) return true; // winelse if (a[x] y) return false; // losereturn true; // win
}int main()
{memset(a, -1, sizeof a);memset(st, false, sizeof st);a[0] 0;int cur 1;for (int i 1; i N; i ){if (st[i]){/// if (i 20) printf(I%d, st\n\ta[i], i);a[i] -1;}else{/// if (i 20) printf(I%d, No_St\n\ta[i], i);a[i] i cur;if (i cur N)st[i cur] true; // 注意这个cur ;}/// if (i 20) cout a[i] endl;}
/*cout a[0] endl;for (int i 0; i 9; i ){printf(i%d, a[i]%lld\n, i, a[i]);}
*/int t; cin t;int x, n, mina, maxb;while (t -- ){scanf(%d%d, n, x);mina x - 1, maxb n - x;if (mina maxb) swap(mina, maxb);/// printf(a%d, b%d\n, mina, maxb);if (Check(mina, maxb))/// cout \t##win\n,cout yo xi no forever! endl;else/// cout \t##lose\n,cout ma la se mi no.1! endl;}return 0;
}成绩查询ing
原题信息 解题思路
思路很清晰的模拟题就是排序查找不会stl顶多就是再加一个二分 但是 时间很卡 应该使用快读 来解决时间的问题考试的时候没有板子就T了
AC代码
#include bits/stdc.h
using namespace std;
const int BASE1 10, BASE2 10000;
mapstring, int t1;
setstring t2[101];int n, m, opt;inline int IntRead()//内联函数稍微快一点点
{char ch getchar();int s 0, w 1;while(ch 0 || ch 9){if(ch -) w -1;ch getchar();}while(ch 0 ch 9){s s * 10 ch - 0,ch getchar();}return s * w;
}inline string StringRead()
{string str;char s getchar();//处理多余回车或空格while (s || s \n || s \r){s getchar();}//不断读入直到遇到回车或空格while (s ! s ! \n s ! \r){str s;s getchar();}return str;
}inline void StringWrite(std::string str)
{int i 0;while (str[i] ! \0){putchar(str[i]), i;}
}inline void IntWrite(int s)
{int k 0, len 0;if (s 0)putchar(0);while (s){k k * 10 s % 10;s / 10, len;}for (int i 0;i len;i){putchar(k % 10 0);k / 10;}
}int main()
{cin n;string _name; int _id, _sex, _grade;for (int i 1; i n; i ){_name StringRead();_grade IntRead(), _sex IntRead(), _id IntRead();t2[_grade].insert(_name);t1[_name] _sex BASE1 * _grade BASE2 * _id;}cin m;while (m -- ){opt IntRead();if (opt 1){_name StringRead();static int num;num t1[_name];printf(%d %d %d\n, num % BASE2 / BASE1, num / BASE2, num % BASE1);}else{_grade IntRead();static setstring::iterator it;for (it t2[_grade].begin(); it ! t2[_grade].end(); it ){StringWrite(*it);putchar(\n);}}}return 0;
}
/*
5
N 28 2 7475
UN 83 2 27550
EXF 28 2 17298
OVYNH 51 2 14827
XNV 53 1 7591
2
1
XNV
2
28
*/
G 贪吃的派蒙
原题信息 解题思路
关键就是改变其他人领取的数量来使得派蒙的前一个人刚刚好领完这是一个 数学 区间 不等式的问题 最后注意上下取整就好
H数羊
原题信息 解题思路
直接打表找规律我是证明半天没出来最后快没时间了才打的表血亏
AC代码
#include bits/stdc.h
using namespace std;const int MOD 998244353;
typedef long long LL;int fun(int x, int y)
{if (x 1 y 0) return 2;else if (x 0 y 0) return 1;else if (x 2 y 0) return x 2;else return fun(fun(x - 1, y), y - 1);
}int qmi(LL a, int k, int MOD)
{LL res 1;while (k){if (k 1){res (res * a) % MOD;}a a * a % MOD;k 1;}return res;
}int cal(int x, int y)
{if(x 1) return 2;if (y 0){return (x 2) % MOD;}else if (y 1){return (x * 2) % MOD;}else{return qmi(2, x, MOD);}
}int main()
{/*for (int i 1; i 18; i ){printf(i%d, , i);for (int j 0; j 2; j ){printf(%d, , fun(i, j));}cout endl;}*/int t; cin t;while (t -- ){static int x, y;scanf(%d%d, x, y);printf(%d\n, cal(x, y));}}I 买花
原题信息 解题思路
直接就是 2i2^i2i 的前缀和但是要注意 不可以是一天的
AC代码
#include bits/stdc.h
using namespace std;int a[200];bool Check(int x)
{for (int i 2; i 15; i ){if (x % a[i] 0)return true;}return false;
}int main()
{a[1] 1;for (int i 2; i 15; i ){a[i] (a[i - 1] 1);}for (int i 1; i 15; i )a[i] a[i - 1] a[i];int t; cin t;while (t -- ){static int n;scanf(%d, n);if (Check(n)){puts(YE5);}else{puts(N0);}}return 0;
}
J 这是一题简单的模拟
原题信息 解题思路
直接就是模拟就行了关键是题目描述的不太清楚多读几遍 就好了 对于一个可行的道路必须要经过所有的城市是N个不是n个
AC代码
#include cstdio
#include cstring
#include algorithm
#include iostream
using namespace std;const int N 310, INF 0x3f3f3f3f;
int n, m;
int e[N][N];
bool st[N];
int k;
int path[N * 1000];
int res INF;int main()
{cin n m;memset(e, 0x3f, sizeof e);for (int i 1; i m; i ){static int x, y, w;scanf(%d%d%d, x, y, w);e[x][y] e[y][x] w;}cin k;res INF;int tmpres;while (k -- ){tmpres 0;static int n2; scanf(%d, n2);for (int i 1; i n2; i )scanf(%d, path[i]);if (n2 ! n)continue;n2 ; path[n2] 0;path[0] 0;memset(st, false, sizeof st);for (int i 1, pre, cur; i n2; i ){pre path[i - 1], cur path[i];if (st[cur] true){tmpres INF;break;}st[cur] true;if (e[pre][cur] INF){tmpres INF;break;}tmpres e[pre][cur];}res min(res, tmpres);}if (res INF) res -1;cout res endl;return 0;
}
K黑洞密码
原题信息 解题思路
就是一个简单的字符串问题和模拟相关注意 字母谁在谁的后面特判就好
AC代码
#include bits/stdc.h
using namespace std;const int N 100;
int num[N];
char str[N];
char s[N];
int nidx, cidx;char Change(char ch, int num)
{if (ch A ch Z){if (ch num Z) return ch num;else return ch num - Z - 1 b;}else{if (ch num z) return ch num;else return ch num - z - 1 B;}
}int main()
{nidx cidx 0;cin str;for (int i 0; i 32; i ){if (str[i] 0 str[i] 9){num[nidx ] str[i] - 0;}else{s[cidx ] str[i];}}for (int i 0; i 16; i ){s[i] Change(s[i], num[i]);}for (int i 0; i 4; i ){for (int j 3 i * 4; j i * 4; j -- ){cout s[j];}}cout endl;return 0;
}
L建立火车站
原题信息 解题思路
求最大值最小典型的 二分
AC代码
#include bits/stdc.h
using namespace std;typedef long long LL;
const int N 100010;LL a[N];
LL n, k;bool Check(LL l, LL k)
{if (l 0){for (int i 2; i n; i ){if (a[i] ! a[i - 1]) return false;}return true;}LL dist;for (int i 2; i n; i ){dist a[i] - a[i - 1];k k - (dist - 1) / l;if (k 0) return false;}return true;
}int main()
{cin n k;for (int i 1; i n; i )scanf(%lld, a[i]);sort(a 1, a n 1);LL l, r, mid;l 0, r 1e1210;while (l r){mid l r 1;if (Check(mid, k)){r mid;}else{l mid 1;}}cout l endl;return 0;
}
心得体会
题目信息要读懂读清楚不要漏掉信息结合样例
空间开的足够LL信息需要注意
输出的字符串YESNO不要自己打直接复制粘贴
快读卡时间记得打板子
double精度很高的不必转换为整数求二进制信息
一些数学题目先打表找规律别直接推导
