新手学做网站pdf下载,企业网站建设的要求,自己用自己电脑做网站空间,建站网站一#xff0c;赛中得分
T1100T2100T350T440总分290 二#xff0c;赛中概括
T1T2较快过#xff0c;T3T4骗了90分#xff08;意料之中#xff0c;这么好骗分#xff01;#xff01;#xff01;#xff09;。
三#xff0c;题目解析 涂格子(paint) 问题描述 现在有…一赛中得分
T1100T2100T350T440总分290 二赛中概括
T1T2较快过T3T4骗了90分意料之中这么好骗分。
三题目解析 涂格子(paint) 问题描述 现在有一个 n 行 m 列的网格纸一开始每个格子都是白色的。 现在你可以任意挑选恰好 x 行和 y 列将挑选的整行整列上的每一个格子涂成黑色 问剩下多少个格子是白色的。 输入格式 第一行为 n,m,x,y含义如上所示。 输出格式 一行一个整数表示答案。 样例输入 5312 样例输出 4 数据分布 对于 60% 的数据:1≤n,m≤100对于 100% 的数据:1≤n,m≤10^9(1000000000),1≤x≤n,1≤y≤m 较简单一道数学题不脑残就能过
AC代码
#includebits/stdc.h
using namespace std;
int main(){freopen(paint.in,r,stdin);freopen(paint.out,w,stdout);long long n,m,x,y;cinnmxy;coutn*m-n*y-x*(m-y);//算出结果return 0;
} 数串串(aba) 问题描述 给定一个长度为 n 的字符串求有多少个长度为 3 的子序列满足形如 ABA 的格式即子序列中的第一个字母等于第三个字母但它们都不等于第二个字母。 由不同位置的相同字符构成的子序列被认为是不同的子序列见样例解释。 一个序列被称为字符串 s 的子序列当且仅当该序列能仅通过 s 删除一部分字符得到。 输入格式 第一行一个正整数 n 表示字符串的长度。 第二行一个长度为 n 的字符串保证字符串仅由小写英文字母构成。 输出格式 一行一个整数表示答案。 样例输入 7abacabc 样例输出 9 样例解释 满足条件的子序列有 aba,aba,aca,aca,bab,bab,bcb,cac,cbc 共 9 个。 数据分布 对于 10% 的数据满足 n≤300 ; 对于 60% 的数据满足 n≤5×10^4(50000) ; 对于 100% 的数据满足 1≤n≤10^6(1000000) 。 不会的人可以先参考一下两道题 题目大意 给定一个字符串请计算ac作为字符串子序列出现的次数 注意字符串子序列指的是从最初字符串通过去除某些元素但不破坏余下元素的相对位置在前或在后而形成的新序列。例如acf、bde、bcd都是abcdef的子序列而cae并不是。 样例 输入 aaaccc 输出 9 题目解析 可以从前往后计算有多少个a把每个c的地方出现了几个a加起来也可以从后往前计算有多少个c把每个a的地方出现了几个c加起来。 AC代码 #include bits/stdc.h
using namespace std;
int main() {//freopen(acok.in,r,stdin);//freopen(acok.out,w,stdout);string a;cina;int ba.size(),cnt0,ans0;int c[b]{0};for(int i0;ib;i){if(a[i]a){ans;}c[i]ans;if(a[i]c)cntc[i];}coutcnt;//fclose(stdin);//fclose(stdout);return 0;
} 扩展输入长度和字符串求里面有多少个cow。 思路用枚举循环在字符串中正序查找O左边C的个数用枚举循环在字符串中倒序查找O右边W的个数把他们相乘最后相加。 样例 输入 6 coowww 输出 6 AC代码 #includebits/stdc.h
using namespace std;
long long c[100005],d[100005];
int main(){int n;cinn;string a;cina;long long cnt0,ba.size();long long ans0;for(int i0;ib;i){if(a[i]C)ans;c[i]ans;}ans0;for(int ib-1;i0;i--){if(a[i]W)ans;d[i]ans;}for(int i0;ib;i){if(a[i]O){cntc[i]*d[i];}}coutcnt;return 0;
} 与上面两道题的思路一样 AC代码 #includebits/stdc.h
using namespace std;
long long n,b[1000006],c[1000006],cntt0;
int main(){freopen(aba.in,r,stdin);freopen(aba.out,w,stdout);string a;cinna;for(char ia;iz;i){memset(b,0,sizeof(b));memset(c,0,sizeof(c));long long ans0,cnt0,sum0;for(int j0;jn;j){if(a[j]i)ans;b[j]ans;}for(int jn-1;j0;j--){if(a[j]i)cnt;c[j]cnt;}for(int j0;jn;j){if(a[j]!i){sumc[j]*b[j];}}cnttsum;}coutcntt;return 0;
} 取石子(pick) 问题描述 有 n 堆石头排成一行第 i 堆中有 ai 颗石子Alice 和 Bob 打算玩一个取石子的博弈游戏他们为每堆石子赋予了一个权值 bi并规定一次操作为选定一堆石子从它本身和它前面的所有石子堆中各取走一颗。当前面有的石子堆中已经无石子的时候不允许这样操作。对第 i 堆石子进行操作可以获得权值 bi。每堆石子对应的操作只能做 11 次。 现在他们不想玩无趣的博弈游戏了他们想知道如果他们不断进行这样的操作直到没有任何操作可以进行在最优情况下一共能获得多少权值。 形式化来说给定 n 长序列 a1,a2,⋯,an一次操作为选定一个 x使a1,a2,⋯,ax 均减少 1但不允许选择会将某个 ai 减成负数的 x操作完成之后获得权值 bx每种 x 最多只能被选定 1 次求经过任意多次操作之后能获得的最大权值。 输入格式 第一行为石子堆数 n 第二行为 n 个整数 a1,a2,⋯,an 第三行为 n 个整数 b1,b2,⋯,bn 输出格式 一行一个整数可获得的最大权值和 样例输入 56 2 2 1 11 3 2 4 5 样例输出 9 样例解释 可以对第 1,2,5 堆石子分别进行一次操作共获得权值 1359最后的石子堆情况为 3 0 1 0 0 数据分布 对于 100% 的数据1≤n≤5000,1≤ai≤10^9(1000000000),1≤bi≤10^5(100000) 对于 30% 的数据有额外限制1≤n≤20 对于另外 30% 的数据有额外限制对于所有的 i,bi1 动态规划 AC代码 #includebits/stdc.h
using namespace std;
long long n,a[5005],b[5005],cnt0,dp[5005][5005];
int main(){//freopen(pick.in,r,stdin);//freopen(pick.out,w,stdout);cinn;for(int i1;in;i){cina[i];}for(int i1;in;i){cinb[i];}memset(dp,-1,sizeof(dp));for(int i0;in;i){dp[0][i]0;}for(int i1;in;i){for(long long j0;jn;j){dp[i][min(a[i],j)]max(dp[i][min(a[i],j)],dp[i-1][j]);}if(a[i]0){for(long long j1;jn;j){if(dp[i-1][j]!-1)dp[i][min(a[i]-1,j-1)]max(dp[i-1][j]b[i],dp[i][min(a[i]-1,j-1)]);}}}for(int i0;in;i){cntmax(cnt,dp[n][i]);}coutcntendl;return 0;
} 健身计划(gym) 问题描述 Setsuna 想要运动 于是她安排了 n 天内的作息作息用一个 01 字符串 s 表示若 si 为 0 则表示这天休息为 11 则表示这天要去健身房运动。 但是连续 x 天的运动会积累 x(x1)/2 点疲劳值也就是说字符串中每段长度为 x 的极长连续 1 会带来 x(x1)/2 点疲劳值。 例如若她的安排为 11101011 那疲劳值为 23(31)21(11)22(21)10 点。 现在她可以把任意天运动日改成休息日问最少需要改几天才能使得疲劳值小于等于 k。 输入格式 第一行包含两个整数 n,k 。 第二行包含一个长度为 n 的 01 串 s。 输出格式 输出一个整数表示答案。 样例输入1 7 41110111 样例输出1 2 样例输入2 3 1111 样例输出2 2 数据分布 对于 15% 的数据满足 n≤15 ; 对于 40% 的数据满足 n≤300 ; 对于 60% 的数据满足 n≤2000 ; 对于 100% 的数据满足 1≤n≤10^5(100000),0≤k≤2n(n1) 。 优先队列 AC代码 #includebits/stdc.h
using namespace std;
long long n,m,cnt0,t0;
long long pilao(long long x){return x*(x1)/2;
}
long long cal(long long l,long long k){if(lk)return 0;l-k;k;return l%k*pilao(l/k1)(k-l%k)*pilao(l/k);
}
struct node{int len,k;node(int lenn0,int kk0){lenlenn;kkk;}bool operator(const node p) const {long long xcal(len,k)-cal(len,k1);long long ycal(p.len,p.k)-cal(p.len,p.k1);return xy;}
};
priority_queuenode q;
int main(){//freopen(gym.in,r,stdin);//freopen(gym.out,w,stdout);int now0;cinnm;for(int i1;in;i){int x;scanf(%1d,x);if(x)cnt;if(!x||in){if(cnt){q.push(node(cnt,0));nowpilao(cnt);}cnt0;}}long long ans0;while(nowm){ans;node tmpq.top();q.pop();now-cal(tmp.len,tmp.k)-cal(tmp.len,tmp.k1);q.push(node(tmp.len,tmp.k1));}coutans;return 0;
}
