如何做seo和网站,ui设计公司官网,电子商务师证报考官网,推广普通话的意义A#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/372/A 来源#xff1a;牛客网
某天#xff0c;一只可爱的肥橘喵在路上走#xff0c;突然遇到了一个怪人#xff0c;那怪人自称PM6#xff0c;“小肥喵#xff0c;这里有一道水题#xff0c;答对…A
链接https://ac.nowcoder.com/acm/contest/372/A 来源牛客网
某天一只可爱的肥橘喵在路上走突然遇到了一个怪人那怪人自称PM6“小肥喵这里有一道水题答对了我就请你吃狗肉答错了你就请我吃猫肉”
喵咪瑟瑟发抖“QAQ什么题”
PM6道“给你坐标轴上的N个点求出对于每个点有多少个点的 X 坐标和 Y 坐标都大于它。”
毫不意外蠢肥喵完全不会这道题并面临着被做成猫肉火锅的危险求求你救救喵咪
输入描述:
输入包括两行第一行是正整数n表示点数接下来N行每行两个数表示第i个点的横坐标和纵坐标坐标值都是整数输入数据中存在坐标相同的点。
对于50%的数据0点的坐标大小100000N100
对于100%的数据0点的坐标大小100000N1000
输出描述:
输出包括N行第i行表示有多少个点在点i的右上方。
示例1
输入
复制
3
1 2
2 3
4 4
输出
复制
2
1
0
解题报告 暴力没啥好说的。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
pairint,int p[MAX];
int main()
{int n;cinn;for(int i 1; in; i) {scanf(%d%d,p[i].first,p[i].second);}for(int i 1; in; i) {int ans 0;for(int j 1; jn; j) {if(p[j].first p[i].first p[j].second p[i].second) ans;}printf(%d\n,ans);}return 0 ;
B
题干
链接https://ac.nowcoder.com/acm/contest/372/B 来源牛客网
某天一只可爱的小兔砸在路上蹦蹦跳跳地走着怪人PM6出现了于是小兔子被盯上了。
PM6“免子。哦不小兔子。你长得真好…不对真可爱。我这里有一道很容易很容易的题目答对了我就请你吃萝卜答错了你就请我吃兔肉好不好呀~~”
小兔砸“萝卜好呀好呀好呀。”于是笨笨的兔纸入套了。
PM6“我这里有一个由 N 个数组成的序列给你 M 个询问每个询问会给你一个数 X 对于每个询问你要回答出序列中与这个值最接近的元素。”
听完题后兔子吓成一坨免子了面临着变成红烧兔头的危险求求你救救兔子
输入描述:
第一行包含一个整数N为序列长度。
第二行包含N个整数为序列各元素。
第三行包含一个整数M为PM6的询问个数。
接下来M行每行一个整数X为要询问最接近元素的给定值。
对于40%的数据1N100001M1000
对于另外10%的数据M1
对于100%的数据1 N 1000001M100000序列中的每个数X1e9
输出描述:
M行每行有一个整数为最接近相应给定值的元素值保持输入顺序。若有多个值满足条件输出最小的一个。
示例1
输入
复制
5
2 4 5 5 7
3
2
5
6
输出
复制
2
5
5
解题报告 二分就好了注意特判第一个数和最后一个数因为这两个不能用下面那个通式因为可能pos-10 或者posn1此时不能放到数组中取对应数因为都是0貌似很多人因为没有特判所以80分了这题。。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
int a[MAX];
int main()
{int n,m;cinn;for(int i 1; in; i) scanf(%d,ai);sort(a1,an1);cinm;while(m--) {int x;scanf(%d,x);int pos lower_bound(a1,an1,x) - a;if(pos 1) {printf(%d\n,a[1]);continue;}if(pos n1) {printf(%d\n,a[n]);continue;}if(abs(a[pos] - x) abs(a[pos-1]-x)) printf(%d\n,a[pos-1]);else printf(%d\n,a[pos]);}return 0 ;} C
题干
链接https://ac.nowcoder.com/acm/contest/372/C 来源牛客网
另一天一只可爱的围着围巾的肥企鹅在路上摇摇晃晃地走着遇上了迎面走来的打着饱嗝的PM6。小企鹅预感不妙这不就是最近有名的恶人PM6么吓得立刻扭头就想跑。
PM6“小火汁站住我不吃你谁叫你是保护动物。我这有一道简单题如果你答对了我就给你吃鱼肉如果你答错了就免费帮我充游戏币”
企鹅“_(:3J∠)_默默摘掉围巾”
PM6“我给你一个文本串 S 再给你两个串A、B你要将文本串中的 A 都转换成 B 转换后的字符不再参与转换输出最终的文本串。”
求求你救救企鹅
输入描述:
第一行输入一个文本串 S 。
第二行输入字符串 A 。
第三行输入字符串 B 。
|S|为S的长度|A|为A的长度|B|为B的长度所有字符都是小写字母保证 |A| |S| 。
对于50%的数据1 |A|、|B|、|S| 1000
对于100%的数据1 |A|、|B|、|S| 1000000
输出描述:
只有一行输出转换后的文本串。
示例1
输入
复制
abababcd
ab
cd
输出
复制
cdcdcdcd
解题报告 KMP就好了记录下来每一个匹配的第一个位置然后遍历整个字符串遇到匹配的位置的时候就输出替换串直到遍历完第一个字符串。
AC代码
#includecstdio
#includecstring
#define ll long long
using namespace std;
char s[1000005];
char t[1000005];
char ac[1000005];
int Next[1000005];
int ans[1000005];
int len1,len2,cnt;
void getnext() {int j 0,k -1;Next[0] -1;while(jlen2-1) {if(k -1 || t[j] t[k]) {j,k;Next[j] k;} else k Next[k];}
}
int kmp() {int i0,j0;while(i len1) {if(j -1 || s[i] t[j]) {i,j;} else {jNext[j];}if(j len2) {ans[cnt] i-len2;j0;}}return cnt;}
int main() {scanf(%s,s);scanf(%s,t);scanf(%s,ac);len1 strlen(s);len2 strlen(t);getnext();kmp();//printf(%d\n,kmp());int cur 1;int i 0;//cout ans** ans[1]endl;while(1) {if(i len1) break;if(cur cnt) {while(i ans[cur]) {printf(%c,s[i]);i;}cur;i len2;printf(%s,ac);}else {printf(%c,s[i]),i;} }return 0;
} 题干
链接https://ac.nowcoder.com/acm/contest/372/D 来源牛客网
可能很多人要吐槽为什么标题不是“救救blabla”了。
怪人PM6喜欢数糖纸不同的糖纸有不同的颜色一共有 N 张糖纸第 i 张糖纸颜色为 Ci 它们的位置都是固定的。PM6喜欢五彩缤纷的糖纸所以他不希望有重复的颜色。他有一次机会可以收集任意一段连续区间内的糖纸。求出PM6最多能收集多少张糖纸。
输入描述:
第一行一个正整数 N 表示共有 N 张糖纸。
第二行共有 N 个正整数第 i 个正整数表示第 i 张糖纸的颜色 Ci
对于20%的数据1N100
对于40%的数据1N1000
对于100%的数据1N1e60Ci1e9
输出描述:
一个整数表示PM6最多能收集多少张糖纸。
示例1
输入
复制
5
1 2 2 3 4
输出
复制
3
说明
PM6可以收集第3到第5张的糖纸共有三张。
解题报告 尺取法。
AC代码每次固定右边界来移动左边界
#includestdio.h
#includeiostream
#includealgorithm
#includestring.h
using namespace std;
#define maxn 1000000
int a[maxn5];
bool b[1000000005];
int main()
{int n;scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);int l0,ans1;for(int i1;in;i){while(b[a[i]])b[a[l]]false;b[a[i]]true;ansmax(ans,i-l);}printf(%d\n,ans);return 0;
}
AC代码2固定左边界看可以到达的右边界
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e6 5;
const int FFF 5e7 6;
int mp[MAX];
int cnt,a[MAX];
bool vis[FFF];
int HH(int x) {return (1LL*13531*x)%(FFF-100);
}
int main()
{int n;cinn;for(int i 1; in; i) scanf(%d,a[i]),mp[i] HH(a[i]);int l 1,r 1,ans 0;while(lr l n) {while(vis[mp[r]] 0 r n) {vis[mp[r]] 1,r;}ans max(ans,r-l);vis[mp[l]] 0;l;}printf(%d\n,ans);return 0 ;}
这个实现方法很多可以Hash可以直接开1e9的数组可以unordered_map可以用二分来离散化但是离散化完了要重新记录到一个数组中这样使用的时候是O1的不能每次使用都从重新计算因为常数有点扛不住、、
并且Hash的时候注意不能用rand()不然可能本来相同的值可能就会被映射到不同地方去了。
这样写显然错误越界了
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e6 5;
const int FFF 5e7 6;
int mp[MAX];
int cnt,a[MAX];
bool vis[FFF];
int HH(int x) {return (1LL*13531*x)%(FFF-1);
}
int main()
{int n;cinn;for(int i 1; in; i) scanf(%d,a[i]),mp[a[i]] HH(a[i]);int l 1,r 1,ans 0;while(lr l n) {while(vis[mp[a[r]]] 0 r n) {vis[mp[a[r]]] 1,r;}ans max(ans,r-l);vis[mp[a[l]]] 0;l;}printf(%d\n,ans);return 0 ;}
常数很小的unordered_map400ms我写的就800ms、、
#includecstdio
#includeunordered_map
using namespace std;int main()
{unordered_mapint,intpos;int n,x,now0,ans1;scanf(%d,n);for(int i1;in;i){scanf(%d,x);nowi-pos[x]now?now1:i-pos[x];ansansnow?ans:now;pos[x]i;}printf(%d\n,ans);return 0;
}
还可以直接取模
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
#define N 1000001
#define P 1651469
int n,a[N],ans0;
bool v[N*2];
int main() {cinn;for(int i1;in;i) scanf(%d,a[i]);int l1,r1;v[a[1]%P]1;while(rn) {if(v[a[r1]%P]) {while(a[r1]!a[l])v[a[l]%P]0;l;}v[a[r]%P]1;ansmax(ans,r-l1);}coutansendl;
} 写在后面 纪念第一场ak...虽然题目很水但毕竟是不熟悉的OI赛制。继续加油
