p2p网站建设时间,网络营销的多种形式和特点,网页定做,网站建设哪家好 思创网络目录
T1
题目描述
输入格式
输出格式
代码
T2
题目描述
输入格式
输出格式
题目描述
输入格式
输出格式
题意翻译
代码
T3
题目背景
题目描述
输入格式
输出格式
代码
T4
题目描述
输入格式
输出格式
总结 T1 题目描述 小 Y 有一把五个拨圈的密码锁。…目录
T1
题目描述
输入格式
输出格式
代码
T2
题目描述
输入格式
输出格式
题目描述
输入格式
输出格式
题意翻译
代码
T3
题目背景
题目描述
输入格式
输出格式
代码
T4
题目描述
输入格式
输出格式
总结 T1 题目描述 小 Y 有一把五个拨圈的密码锁。如图所示每个拨圈上是从 00 到 99 的数字。每个拨圈都是从 00 到 99 的循环即 99 拨动一个位置后可以变成 00 或 88 因为校园里比较安全小 Y 采用的锁车方式是从正确密码开始随机转动密码锁仅一次每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。 当小 Y 选择同时转动两个相邻拨圈时两个拨圈转动的幅度相同即小 Y 可以将密码锁从 0 0 1 1 5 转成 1 1 1 1 5但不会转成 1 2 1 1 5。 时间久了小 Y 也担心这么锁车的安全性所以小 Y 记下了自己锁车后密码锁的 n 个状态注意这 n 个状态都不是正确密码。 为了检验这么锁车的安全性小 Y 有多少种可能的正确密码使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部 n 个状态。 输入格式 输入的第一行包含一个正整数 n表示锁车后密码锁的状态数。 接下来 n 行每行包含五个整数表示一个密码锁的状态。 输出格式 输出一行包含一个整数表示密码锁的这 n 个状态按照给定的锁车方式能对应多少种正确密码。 这道题第一眼看是数学
当n1时一定会输出81
当n1时如果任意两组的差异有一组大于二那么输出0如果任意两组的差异为二就要判断他们是否相邻且差值是否相同若不成立则输出0否则输出10如果任意两组的差异为一就要判断是否在同一位置相差如果是输出10否则输出1。 后来试了试。。。还是暴力只不过是暴力枚举求交集
下面直接暴搜上代码
代码
#includebits/stdc.h
using namespace std;
const int N 10;
int n, ans;
int st[N], ce[N][10];int dis(int x, int y, int xb, int yb) {int ddd (x - xb 10) % 10;int dd2 (y - yb 10) % 10;//cout ddd dd2 endl;return (ddd dd2);
}int calc(int id) {int cnt 0;int id1 0, id2 0;for(int i 1; i 5;i) {if(st[i] ce[id][i]) continue;if(!id1) id1 i;else if(!id2) id2 i;cnt;}if(cnt 1) return 1;if(cnt 2) return 0;//cout id1 id2 endl;if(id1 ! id2 - 1 id1 ! id2 1) return 0;for(int i 1; i 5;i) {if(st[i] ! ce[id][i] st[i 1] ! ce[id][i 1]) {if(!dis(st[i], st[i 1], ce[id][i], ce[id][i 1])) return 0;}}return 1;
}void did() {//for(int i 1;i 5;i) cout st[i] ;//cout endl;for(int i 1;i n;i) {if(!calc(i)) return;}ans;
}void dfs(int i) {if(i 5) return did();for(int j 0;j 9;j) {st[i] j;dfs(i 1);st[i] 0;}}int main() {scanf(%d, n); for(int i 1; i n;i) {for(int j 1;j 5;j) {scanf(%d, ce[i][j]);}}dfs(1);printf(%d, ans);return 0;
} T2 题目描述 小 L 现在在玩一个低配版本的消消乐该版本的游戏是一维的一次也只能消除两 个相邻的元素。 现在他有一个长度为 n 且仅由小写字母构成的字符串。我们称一个字符串是可消除的当且仅当可以对这个字符串进行若干次操作使之成为一个空字符串。 其中每次操作可以从字符串中删除两个相邻的相同字符操作后剩余字符串会拼接在一起。 小 L 想知道这个字符串的所有非空连续子串中有多少个是可消除的。 输入格式 输入的第一行包含一个正整数 n表示字符串的长度。 输入的第二行包含一个长度为 n 且仅由小写字母构成的的字符串表示题目中询问的字符串。 输出格式 输出一行包含一个整数表示题目询问的答案。 这道题和CF重了所以也贴一下CF的题面 题目描述 Lets look at the following process: initially you have an empty stack and an array s of the length l . You are trying to push array elements to the stack in the order s1,s2,s3,…sl . Moreover, if the stack is empty or the element at the top of this stack is not equal to the current element, then you just push the current element to the top of the stack. Otherwise, you dont push the current element to the stack and, moreover, pop the top element of the stack. If after this process the stack remains empty, the array s is considered stack exterminable. There are samples of stack exterminable arrays: [1,1][1,1] ;[2,1,1,2][2,1,1,2] ;[1,1,2,2][1,1,2,2] ;[1,3,3,1,2,2][1,3,3,1,2,2] ;[3,1,3,3,1,3][3,1,3,3,1,3] ;[3,3,3,3,3,3][3,3,3,3,3,3] ;[5,1,2,2,1,4,4,5][5,1,2,2,1,4,4,5] ; Lets consider the changing of stack more details if s[5,1,2,2,1,4,4,5] (the top of stack is highlighted). after pushing s15 the stack turn into [5][5] ;after pushing s21 the stack turn into [5,1][5,1] ;after pushing s32 the stack turn into [5,1,2][5,1,2] ;after pushing s42 the stack turn into [5,1][5,1] ;after pushing s51 the stack turn into [5][5] ;after pushing s64 the stack turn into [5,4][5,4] ;after pushing s74 the stack turn into [5][5] ;after pushing s85 the stack is empty. You are given an array a1,a2,…,an . You have to calculate the number of its subarrays which are stack exterminable. Note, that you have to answer q independent queries. 输入格式 The first line contains one integer q ( 1≤q≤3⋅105 ) — the number of queries. The first line of each query contains one integer n ( 1≤n≤3⋅105 ) — the length of array a . The second line of each query contains n integers a1,a2,…,an ( 1≤ai≤n ) — the elements. It is guaranteed that the sum of all n over all queries does not exceed 3⋅1053⋅105 . 输出格式 For each test case print one integer in single line — the number of stack exterminable subarrays of the array a . 题意翻译 给一个序列进行栈操作从左到右入栈若当前入栈元素等于栈顶元素则栈顶元素出栈否则当前元素入栈。若进行完操作后栈为空这说这个序列是可以被消除的。 给你一个长度为n的序列a问a有多少子串是可以被消除的。 这道题用括号匹配O(2^{_{n}})做能得50分
但是我们要冲正解
我们考虑保存一个mi,j 表示一个最大的 mi,j 满足 mi,jj 且mi,j1,i 可以消除然后就可以快速求 pi 了。
那么怎么维护 m 呢我们如果找到了合法的 pi可以考虑直接令 mimpi−1看似时间复杂度爆炸其实后面用不到mpi−1可以直接交换时间复杂度为 O(1)然后再把不同的项改改就行了。
下面上代码
代码
#includebits/stdc.h
#define int long long
using namespace std;
string s;
int n, ans, a[2000005], p[2000005], f[2000005];
mapint, int m[2000005];
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);scanf(%lld, n);cin s;for (int i 0; i n; i) {a[i 1] s[i] - a;m[i 1].clear();f[i 1] 0;p[i 1] -1;}for (int i 1; i n; i) {if (m[i - 1].count(a[i])) {int t m[i - 1][a[i]];p[i] t;swap(m[i], m[t - 1]);if (t ! 1) {m[i][a[t - 1]] t - 1;}}m[i][a[i]] i;}for (int i 1; i n; i) {if (p[i] -1) {continue;}f[i] f[p[i] - 1] 1;ans f[i];}printf(%lld\n, ans);return 0;
} T3 题目背景 在 C 等高级语言中除了 int 和 float 等基本类型外通常还可以自定义结构体类型。在本题当中你需要模拟一种类似 C 的高级语言的结构体定义方式并计算出相应的内存占用等信息。 题目描述 在这种语言中基本类型共有 44 种byte, short, int, long分别占据 1,2,4,81,2,4,8 字节的空间。 定义一个结构体类型时需要给出类型名和成员其中每个成员需要按顺序给出类型和名称。类型可以为基本类型也可以为先前定义过的结构体类型。注意定义结构体类型时不会定义具体元素即不占用内存。 定义一个元素时需要给出元素的类型和名称。元素将按照以下规则占据内存 元素内的所有成员将按照定义时给出的顺序在内存中排布对于类型为结构体的成员同理。为了保证内存访问的效率元素的地址占用需要满足对齐规则即任何类型的大小和该类型元素在内存中的起始地址均应对齐到该类型对齐要求的整数倍。具体而言 对于基本类型对齐要求等于其占据空间大小如 int 类型需要对齐到 44 字节其余同理。对于结构体类型对齐要求等于其成员的对齐要求的最大值如一个含有 int 和 short 的结构体类型需要对齐到 44 字节。 以下是一个例子以 C 语言的格式书写 struct d {short a;int b;short c;
};
d e;该代码定义了结构体类型 d 与元素 e。元素 e 包含三个成员 e.a, e.b, e.c分别占据第 0∼10∼14∼74∼78∼98∼9 字节的地址。由于类型 d 需要对齐到 44 字节因此 e 占据了第 0∼110∼11 字节的地址大小为 1212 字节。 你需要处理 n 次操作每次操作为以下四种之一 定义一个结构体类型。具体而言给定正整数 k 与字符串 ,1,1,…,,s,t1,n1,…,tk,nk其中 k 表示该类型的成员数量s 表示该类型的类型名1,2,…,t1,t2,…,tk 按顺序分别表示每个成员的类型1,2,…,n1,n2,…,nk 按顺序分别表示每个成员的名称。你需要输出该结构体类型的大小和对齐要求用一个空格分隔。 定义一个元素具体而言给定字符串 ,t,n 分别表示该元素的类型与名称。所有被定义的元素将按顺序从内存地址为 00 开始依次排开并需要满足地址对齐规则。你需要输出新定义的元素的起始地址。 访问某个元素。具体而言给定字符串 s表示所访问的元素。与 C 等语言相同采用 . 来访问结构体类型的成员。如 a.b.c表示 a 是一个已定义的元素它是一个结构体类型有一个名称为 b 的成员它也是一个结构体类型有一个名称为 c 的成员。你需要输出如上被访问的最内层元素的起始地址。 访问某个内存地址。具体而言给定非负整数addr表示所访问的地址你需要判断是否存在一个基本类型的元素占据了该地址。若是则按操作 3 中的访问元素格式输出该元素否则输出 ERR。 输入格式 第 11 行一个正整数 n表示操作的数量。 接下来若干行依次描述每个操作每行第一个正整数 op 表示操作类型 若 op1首先输入一个字符串 s 与一个正整数 k表示类型名与成员数量接下来 k 行每行输入两个字符串 ,ti,ni依次表示每个成员的类型与名称。 若 op2输入两个字符串 ,t,n表示该元素的类型与名称。 若 op3输入一个字符串 s表示所访问的元素。 若 op4输入一个非负整数 addr表示所访问的地址。 输出格式 输出 n 行依次表示每个操作的输出结果输出要求如题目描述中所述。 这道题在考场上想做又不敢做纠结了很久。下来一想才发现是纯纯的大模拟。
废话不多说直接上代码模拟题别抄
代码
#includebits/stdc.h
#define int long long
using namespace std;
struct Node {int k, s[105], a[105], o[105], maxn, siz;string tp[105], nm[105];string id;
} f[105];
struct node {int s, a, b;string tp, nm;
} g[105];
mapstring, int mp1, mp2, mp;
signed main() {ios::sync_with_stdio(false);mp1[byte] 1, mp1[short] 2, mp1[int] 4, mp1[long] 8, mp2[byte] 1, mp2[short] 2, mp2[int] 4, mp2[long] 8;int cnt 0, tot 0, q;cin q;while (q--) {int op;cin op;if (op 1) {cnt;cin f[cnt].id;cin f[cnt].k;for (int i 1; i f[cnt].k; i) {cin f[cnt].tp[i] f[cnt].nm[i];int lst f[cnt].o[i - 1] f[cnt].s[i - 1];f[cnt].a[i] mp2[f[cnt].tp[i]];f[cnt].s[i] mp1[f[cnt].tp[i]];if (lst % f[cnt].a[i]) {lst (f[cnt].a[i] - lst % f[cnt].a[i]);}f[cnt].o[i] lst;f[cnt].maxn max(f[cnt].maxn, f[cnt].a[i]);}int lst f[cnt].o[f[cnt].k] f[cnt].s[f[cnt].k];if (lst % f[cnt].maxn) {lst (f[cnt].maxn - lst % f[cnt].maxn);}f[cnt].siz lst;mp1[f[cnt].id] f[cnt].siz;mp2[f[cnt].id] f[cnt].maxn;mp[f[cnt].id] cnt;cout f[cnt].siz f[cnt].maxn \n;} else if (op 2) {tot;cin g[tot].tp g[tot].nm;g[tot].a mp2[g[tot].tp];g[tot].s mp1[g[tot].tp];int lst g[tot - 1].b g[tot - 1].s;if (lst % g[tot].a) lst (g[tot].a - lst % g[tot].a);g[tot].b lst;cout g[tot].b \n;} else if (op 3) {string s;cin s;s .;string cat ;int len s.size(), tp;for (int i 0; i len; i) {if (s[i] .) {tp i 1;break;}cat s[i];}int sum 0, abab;for (int i 1; i tot; i) {if (g[i].nm cat) {sum g[i].b;abab mp[g[i].tp];break;}}if (abab 0) {cout sum \n;continue;}cat ;for (int i tp; i len; i) {if (s[i] .) {for (int j 1; j f[abab].k; j) {if (f[abab].nm[j] cat) {sum f[abab].o[j];abab mp[f[abab].tp[j]];break;}}if (abab 0) {break;}cat ;continue;}cat s[i];}cout sum \n;} else {int cat;cin cat;string sum , ty;int abab -1;for (int i 1; i tot; i) {if (g[i].b g[i].s cat g[i].b cat) {abab mp[g[i].tp];cat - g[i].b;sum g[i].nm;ty g[i].tp;break;}}if (abab -1) {cout ERR\n;continue;}if (!abab) {if (mp1[ty] cat) {cout sum \n;} else {cout ERR\n;}continue;}sum .;while (1) {if (cat 0) {cout ERR\n;break;}int ff 0;for (int i 1; i f[abab].k; i) {if (f[abab].o[i] f[abab].s[i] cat f[abab].o[i] cat) {cat - f[abab].o[i];sum f[abab].nm[i];ty f[abab].tp[i];abab mp[f[abab].tp[i]];ff 1;break;}}if (!ff) {cout ERR\n;break;}if (!abab) {if (mp1[ty] cat) {cout sum \n;} else {cout ERR\n;}break;}sum .;}}}return 0;
} T4 题目描述 你是一个森林养护员有一天你接到了一个任务在一片森林内的地块上种树并养护至树木长到指定的高度。 森林的地图有 n 片地块其中 1 号地块连接森林的入口。共有 n−1 条道路连接这些地块使得每片地块都能通过道路互相到达。最开始每片地块上都没有树木。 你的目标是在每片地块上均种植一棵树木并使得 i 号地块上的树的高度生长到不低于 ai 米。 你每天可以选择一个未种树且与某个已种树的地块直接邻接即通过单条道路相连的地块种一棵高度为 0 米的树。如果所有地块均已种过树则你当天不进行任何操作。特别地第 1 天你只能在 1 号空地种树。 对每个地块而言从该地块被种下树的当天开始该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同在第 x 天i 号地块上的树会长高 max(bix×ci,1) 米。注意这里的 x 是从整个任务的第一天而非种下这棵树的第一天开始计算。 你想知道最少需要多少天能够完成你的任务 输入格式 输入的第一行包含一个正整数 n表示森林的地块数量。 接下来 n 行每行包含三个整数 ai,bi,ci分别描述一片地块含义如题目描述中所述。 接下来 n−1 行每行包含两个正整数 ui,vi表示一条连接地块 ui 和 vi 的道路。 输出格式 输出一行仅包含一个正整数表示完成任务所需的最少天数。 这道题我在考场上第一眼想用生长天数进行排序后来才发现x的值会变最后用的贪心骗分。
代码
后续更新等我AC了再说 总结 这套卷子码量太大重点在T2、T4
