第二次参加cf,饮恨两题了
A:大水,分别求出最高的人和最矮的人所在的位置。如果有多个人高度相同且都是最高的话要选靠左边的,有多个人高度相同且都是最矮的话要选靠右边的。然后计算把最高的人和最矮的人分别安排到左边和右边需要走的最短步数即可。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=105;
int num[nMax];
int main(){
int n,i,j,high,low,h,l,ans;
while(scanf("%d",&n)!=EOF){
high=-1;
low=200;
for(i=1;i<=n;i++){
scanf("%d",&num[i]);
if(num[i]>high){ //大的数在左边
high=num[i];
h=i;
}
if(num[i]<=low){ //小的数字在右边
low=num[i];
l=i;
}
}
// cout<<high<<' '<<h<<" "<<low<<" "<<l<<endl;
if(h<l){
ans=h-1+n-l;
}
else{
ans=h-1+n-l-1;
}
cout<<ans<<endl;
}
return 0;
}
B题代码实在太囧~~发出来怕被bs
C:这道本来应该能在最后精彩绝杀的题目却最终饮恨了~~这就叫惜哉剑术疏,奇功遂不成吧。
大致题意就是:如果一个字符串a在打乱排列后可以变成另一个字符串b,则我们称a和b互为anagram,比如“aba”和“aab”就是互为anagram。“aab”和“abc”,“bba”都不互为anagram。
如果有一个带‘?’的字符串a,在把‘?’替换成一些特定的字符后能和字符串b互为anagram,我们称a为good,比如a为“a??”,b为“abc”,则认为a是good。
给出两个长度都是10^5数量级的字符串str1和str2,str1由小写字母和'?'组成,str2由小写字母组成。求出str1中可以分离出多少个good的连续子串。
一开始看到10^5迟迟不敢下手,觉得会tle。后来下了好大决心才写了一个遍历长度为10^5字符串的代码。没想到却pass掉了。比赛测试总数据的时候很囧的被tle掉了。以为是有什么高级牛逼的算法,跟别人对比以后才发现字符串长度的定义少了一个0,杯具啊
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=105;
int cha1[300];
int cha2[300];
bool check(int l){
int need=0;
for(int i='a';i<='z';i++){
if(cha1[i]>cha2[i]){
return 0;
}
need=cha2[i]-cha1[i];
}
if(need==0)return 1;
if(need==cha1['?'])return 1;
}
int main(){
int i,j,len1,len2,ans;
char str1[100005],str2[100005]; //这里这里这里!!
while(scanf("%s%s",str1,str2)!=EOF){
ans=0;
memset(cha2,0,sizeof(cha2));
memset(cha1,0,sizeof(cha1));
len1=strlen(str1); //长串
len2=strlen(str2); //短串
if(len2>len1){
cout<<0<<endl;
continue;
}
for(i=0;i<len2;i++){
cha1[str1[i]]++;
}
for(i=0;i<len2;i++){
cha2[str2[i]]++;
}
for(i=len2-1;i<=len1-1;i++){ //str2尾部所在的位置
// cout<<len2<<" "<<len1<<endl;
if(check(i)){
ans++;
}
cha1[str1[i-len2+1]]--;
cha1[str1[i+1]]++;
}
cout<<ans<<endl;
}
return 0;
}
D是个最短路好题!可惜等到赛后才ac掉~真囧。
给出一个由n个点m条带权边组成的无向图。给出图中的一个点s和一个长度值l。求图中到s点最短距离为l的点的数量,包括节点上的点和边上的点。
首先统计所有节点中距离s最短为l的点的个数,再统计所有边中含有那种点的个数,统计边的时候细节需要特别的注意!!最后输出总和即可。
献上代码:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=600050;
const int mMax=1000050;
const int inf=1<<28;
struct{
int u,v, next;
int w;
}edge[mMax];
int n, k, head[nMax];
int dis[nMax];
int que[nMax],m,sum[nMax];
bool vis[nMax];
void addedge(int a,int b,int w){
edge[k].w = w;
edge[k].u=a;
edge[k].v=b;
edge[k].next=head[a];
head[a]=k;k++;
}
void spfa(int s){ //始点,终点,总点数
int i, hhead = 0, tail = 1; // 长注释的地方就是从最小费用改到最大费用时需要变动的地方
for(i = 0; i <= n; i ++){
dis[i] = inf;////////////
vis[i] = false;
}
dis[s] = 0;
que[0] = s;
vis[s] = true;
while(hhead != tail){
int u = que[hhead];
vis[u] = false;
for(i=head[u];i!=0;i=edge[i].next){//for(i = head[u]; i != 0; i = edge[i].next){
int v = edge[i].v;
if(dis[v] >dis[u] + edge[i].w){////////
dis[v] = dis[u] + edge[i].w;
if(!vis[v]){
vis[v] = true;
que[tail ++] = v;
if(tail == nMax) tail = 0;
//if(++sum[v] > n) return false; // 不包含初始的进栈。
}
}
}
hhead++;
if(hhead ==nMax) hhead = 0;
}
}
int main(){
int i,j,m,s,a,b,c,l,ans,u,v,w,p;
char str[10];
while(scanf("%d%d%d",&n,&m,&s)!=EOF){
k=1;
ans=0;
memset(head,0,sizeof(head));
while(m--){
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
scanf("%d",&l);
spfa(s);
for(i=1;i<=n;i++){
if(dis[i]==l)ans++;
}
for(i=1;i<k;i+=2){
u=edge[i].u;
v=edge[i].v;
w=edge[i].w;
if(dis[u]<l){
if(dis[u]+edge[i].w>l){
p=l-dis[u];
if(dis[v]+w-p>l){
ans++;
}
}
}
if(dis[v]<l){
if(dis[v]+edge[i].w>l){
p=l-dis[v];
if(dis[u]+w-p>l){
ans++;
}
if(dis[u]+w-p==l){
ans++;
}
}
}
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
Codeforces Round #723 (Div. 2).md
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
传说门 刚好今晚是中国场! 其实这道题比较水,但当时思路错,一心想着化简公式,浪费了好多时间a....#pragma GCC optimize(2) #include #define ll long long #define endl '\n' using namespace std; const int manx=
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
传送门 A. EhAb AnD gCd 直接输出1,n-1即可 #include #include #include #include #include #include #include #include #include #include #define pb push_back #define lb lower_bound ...con
题目链接:B. Longest Palindrome 题目 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse....
今天CF被D恶心到了,写个题解重新整理下思路,(20开始想,25写完暴力代码,1.30才过,优化后的。。 核心思路就是在暴力的基础上进行组合数等差加速。 C(n-2,i-1)*C(j-1,n-2)*(i-1) __ j: n-1 -> m 我们发现内层...
-2,4,5,5,6,8 要输出的序列应该是每次从前面选一个,然后从后面选一个 -2,8,4,6,5,5 然后把该序列倒着输出即可 代码: #include #include #include #include #include #include #include #include #...