• Codeforces Round #811 A~F

    A. Everyone Loves to Sleep

    题意：给小明的睡觉时间，给n个闹钟的时间，问能睡多久。

    idea：首先全部转换成分钟进行处理。一个闹钟如果时间早于睡觉时间，那会在第二天同样的时起作用，这时候加上24H就好。最后排个序就有答案了。
    code

    #include
#define LL long long
#define PII pair<LL,LL>
#define x first
#define y second
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
LL work(LL x,LL y)
{
	LL ans = x*60+y;
	return ans;
}

LL n,h,v,tim;
PII a[101];
LL b[101];

void solve()
{
	LL maxx=-1,minn = INF;
	scanf("%lld %lld %lld",&n,&h,&v);
	LL ans = 0 ;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld %lld",&a[i].x,&a[i].y);
	}
	tim = work( h,v );
	for(int i=1;i<=n;i++)
	{
		b[i] = work( a[i].x,a[i].y );
		if( b[i]>=tim ) minn = min( minn , b[i] );
		
		b[i] = work( a[i].x+24,a[i].y );
		if( b[i]>=tim ) minn = min( minn , b[i] );
	}
	LL sum = abs( minn-tim );
	cout<<sum/60<<" "<<sum%60<<endl;
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	int t;
	cin>>t;
	while(t--)
	solve();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50





    B. Remove Prefix

    题意：给一个数组，每次可以删除开头的一个数字,问你几次可以把数组变成没有重复数字的数组

    idea：从最后一个元素开始往前找，出现重复元素就停止，说明在此之前的元素都得删除。

    #include
#define LL long long
#define PII pair<LL,LL>
#define x first
#define y second
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;

int n;
int a[200101];
bool pd[201000];
void solve()
{
	scanf("%d",&n);
	int ans;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	ans = 0;
	for(int i=n;i>=1;i--)
	{
		if( pd[ a[i] ]==false )
		{
			pd[ a[i] ] = true;
		}	
		else
		{
			ans = i;
			break;
		}
	}
	for(int i=ans;i<=n;i++) pd[ a[i] ] = false;
	printf("%d\n",ans);
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	int t;
	cin>>t;
	while(t--)
	solve();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    C. Minimum Varied Number

    题意：给你一个数字n,然后你需要找到一个最小的数字x,使得x的每一位相加之和是n,输出x

    idea：既然要x最小，那么我们可以先从个位开始填大的数字

    code

    #include
#define LL long long
#define PII pair<LL,LL>
#define x first
#define y second
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;

int n,ans[1010],pd[101];
void solve()
{
	cin>>n;
	int tot = 0;
	for(int i=1;i<=9;i++) pd[i] = false;
	while(n)
	{
		for(int i=9;i>=1;i--)
		{
			if( !pd[i] && n-i>=0 )
			{
				pd[i] = true;
				ans[++tot] = i;
				n -= i;
				break;
			}
		}
	}
	for(int i=tot;i>=1;i--)
	{
		cout<<ans[i];
	}
	cout<<endl;
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	int t;
	cin>>t;
	while(t--)
	solve();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    D. Color with Occurrences

    题意：给你一个标准字符串T,给你n个匹配字符串 S S S,如果 S i S_i Si​是T的子串,就可以把T中与 S i S_i Si​相同的字串染色,问你T被全部染色的最小次数是多少,每次选择的是哪一个 S S S

    idea：可以先看一下区间最小覆盖是什么，然后会发现这是板子题。大致就是先把区间按左端点排序，然后每次选择左端点满足要求而且右端点最远的区间更新答案。

    code

    #include
#define LL long long
#define PB push_back
using namespace std;

struct node
{
	int l,r,pos;
}a[101010],ans[101010];

bool cmp(node a,node b)
{
	if( a.l==b.l ) return a.r<b.r;
	else return a.l<b.l;
}

int n,tot;
void solve()
{
	string t,s;
	vector<node> ans;
	tot = 0;
	cin>>t;
//	cout<
	cin>>n;
	int lent = t.size();
	int lens;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		lens = s.size();
		for(int j=0;j<lent-lens+1;j++)
		{
			bool pd = true;
			for(int k=0;k<lens;k++)
			{
				if( s[k]!=t[j+k] )
				{
					pd = false;
					break;
				}
			}
			if( pd )
			{
				tot++;
				a[tot].l = j+1;
				a[tot].r = j+lens-1+1;
				a[tot].pos = i;
			}
		}
	}
	sort( a+1,a+tot+1,cmp );
//	for(int i=1;i<=tot;i++)
//	{
//		cout<
//	}
	int now = 1,l = -1,r = 0;
	while( r<lent )
	{
		l = r+1;
		int tag;
		for(int i=now;i<=tot;i++)
		{
			if( a[i].l<=l && a[i].r>=l )
			{
				if( a[i].r>r )
				{
					r = a[i].r;
					tag = i;
				}
//				r = max( r , a[i].r );
			}
			else if( a[i].l>l )
			{
				now = i;
				break;
			}
		}
		if( r<l )
		{
			printf("-1\n");
			return ;
		}
		else ans.PB( node{ a[tag].pos,a[tag].l } );
	}
	cout<<ans.size()<<endl;
	for(int i=0;i<ans.size();i++)
	{
		cout<<ans[i].l<<" "<<ans[i].r<<endl;
	}
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	int t;
	cin>>t;
	while( t-- )
	{
		solve();
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105

    E. Add Modulo 10

    题意：给一个数组，可以对其中的元素 a i a_i ai​进行操作让 a i = a i + ( a i % 10 ) a_i = a_i + (a_i \quad \% \quad10 ) ai​=ai​+(ai​%10)，问在有限次操作后整个数组的元素可以变成一样的吗。

    idea：首先手推一下会发现操作加的数只跟个位有关，存在这样这样的循环:2 4 8 16 、22 24 28 36，除了0和5，其他的奇数都会加上自身后进入这个循环。同时会发现每一个循环尾数加起来是 ( 2 + 4 + 8 + 6 ) = 20 (2+4+8+6) = 20 (2+4+8+6)=20，就是说如果两个数要经过操作后变成一样，那么这两个数是先跳到尾数一样之后，再一次加20一次加20这样跳的。我们只要先把每个数加到尾数一样，再判断他们模20的值，一样就YES。用set判断有无重复比较方便。

    code

    #include
#define LL long long
using namespace std;

int n;
void solve()
{
	cin>>n;
	set<int> b;
	set<int> c;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		if( x%10==0 )
		{
			b.insert( x );
		}
		else if( x%10==5 )
		{
			b.insert( x+5 );
		}
		else
		{
			while( x%10!=8 )
			{
				x = x+(x%10);
			}
			c.insert(x%20);
		}
	}
	if( b.size()>0 )
	{
		if( b.size()==1&&c.size()==0 )
		{
			printf("Yes\n");
			return ;
		}
		else 
		{
			printf("No\n");
			return ;
		}
	}
	else if( c.size()==1 )
	{
		printf("Yes\n");
		return ;
	}
	else 
	{
		printf("No\n");
		return ;
	}
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	int t;
	cin>>t;
	while( t-- )
	{
		solve();
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    F. Build a Tree and That Is It

    题意：n个点无根树，给定 d i s 1 , 2 d i s 2 , 3 d i s 1 , 3 dis_{1,2} \quad dis_{2,3} \quad dis_{1,3} dis1,2​dis2,3​dis1,3​，问能不能构造出这样的一棵树。

    idea：首先判断一下 d i s 1 , 2 d i s 2 , 3 d i s 1 , 3 dis_{1,2} \quad dis_{2,3} \quad dis_{1,3} dis1,2​dis2,3​dis1,3​需要满足大小关系，不行直接NO。然后我是枚举哪条边最大进行的分类构造。先假设有一个中心点且 d i s 1 , 3 dis_{1,3} dis1,3​最大，这个中心点到点2的距离就是 d i s 1 , 2 + d i s 2 , 3 − d i s 1 , 3 dis_{1,2} + dis_{2,3} - dis_{1,3} dis1,2​+dis2,3​−dis1,3​,同理也可得中心点到点1和点3的距离。然后就可以愉快地构造了。

    code:

    #include
#define LL long long
#define PII pair<int,int>
#define x first
#define y second
#define PB push_back
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;

int n,d[10],maxx = -1,ans[10];
void solve()
{
	vector<PII> v;
	scanf("%d",&n);
	maxx = -1;
	for(int i=1;i<=3;i++)
	{
		scanf("%d",&d[i]);
		maxx = max( maxx , d[i] );
	}
	if( d[3]==maxx )
	{
		if( d[1]+d[2]<d[3] || (d[1]+d[2]-d[3])%2==1 )
		{
			printf("NO\n");
			return ;
		}
		ans[2] = (d[1]+d[2]-d[3])/2;
		ans[1] = d[1] - ans[2];
		ans[3] = d[2] - ans[2];
		int sum = ans[1]+ans[2]+ans[3];
		if( sum+1>n )
		{
			printf("NO\n");
			return ;
		}
		int last = 2,now = 4,tag;
		for(int i=1;i<=ans[2];i++)
		{
			v.PB( make_pair(last,now) );
			last = now;
			now++;
		}
		tag = last;
		
		for(int i=1;i<ans[1];i++)
		{
			v.PB( make_pair(last,now) );
			last = now;
			now++;
		}
		v.PB( make_pair(last,1) );
		
		last = tag;
		for(int i=1;i<ans[3];i++)
		{
			v.PB( make_pair(last,now) );
			last = now;
			now++;
		}
		v.PB( make_pair(last,3) );
		
		last = tag;
		for(;now<=n;)
		{
			v.PB( make_pair(last,now) );
			last = now;
			now++;
		}
	}
	
	else if( d[2]==maxx )
	{
		if( d[1]+d[3]<d[2] || (d[1]+d[3]-d[2])%2==1 )
		{
			printf("NO\n");
			return ;
		}
		ans[1] = (d[1]+d[3]-d[2])/2;
		ans[2] = d[1]-ans[1];
		ans[3] = d[3]-ans[1];
		int sum = ans[1]+ans[2]+ans[3];
		if( sum+1>n )
		{
			printf("NO\n");
			return ;
		}
		int last = 1,now = 4,tag;
		for(int i=1;i<=ans[1];i++)
		{
			v.PB( make_pair(last,now) );
			last = now;
			now++;
		}
		tag = last;
		
		for(int i=1;i<ans[2];i++)
		{
			v.PB( make_pair(last,now) );
			last = now;
			now++;
		}
		v.PB( make_pair(last,2) );
		
		last = tag;
		for(int i=1;i<ans[3];i++)
		{
			v.PB( make_pair(last,now) );
			last = now;
			now++;
		}
		v.PB( make_pair(last,3) );
		
		last = tag;
		for(;now<=n;)
		{
			v.PB( make_pair(last,now) );
			last = now;
			now++;
		}
	}
	
	else if( d[1]==maxx )
	{
		if( d[2]+d[3]<d[1] || (d[2]+d[3]-d[1])%2==1 )
		{
			printf("NO\n");
			return ;
		}
		ans[3] = ( d[2]+d[3]-d[1] )/2;
		ans[1] = d[3]-ans[3];
		ans[2] = d[2]-ans[3];
		int sum = ans[1]+ans[2]+ans[3];
		if( sum+1>n )
		{
			printf("NO\n");
			return ;
		}
		int last = 3,now = 4,tag;
		for(int i=1;i<=ans[3];i++)
		{
			v.PB( make_pair(last,now) );
			last = now;
			now++;
		}
		tag = last;
		
		for(int i=1;i<ans[2];i++)
		{
			v.PB( make_pair(last,now) );
			last = now;
			now++;
		}
		v.PB( make_pair(last,2) );
		
		last = tag;
		for(int i=1;i<ans[1];i++)
		{
			v.PB( make_pair(last,now) );
			last = now;
			now++;
		}
		v.PB( make_pair(last,1) );
		
		last = tag;
		for(;now<=n;)
		{
			v.PB( make_pair(last,now) );
			last = now;
			now++;
		}
	}
	
	printf("YES\n");
	for(int i=0;i<v.size();i++)
	{
		printf("%d %d\n",v[i].first,v[i].second);
	}
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	int t;
	cin>>t;
	while(t--)
	solve();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191

    G. Path Prefixes

    题意：给你n个点,1为根节点 然后给你边,每条边都有两个权值 a i , b i a_i,b_i ai​,bi​从1开始到点 u 路径中的所有边的 ∑ a i \sum a_i ∑ai​ >= 从1开始到点 v 路径中的所有边的 ∑ b i \sum b_i ∑bi​(v是1到u路径中的某个点,同时这个v点的深度尽可能的大) 求出每一个点u对应v的最大深度。

    idea：dfs整棵树，记录一下某点到root的 a i a_i ai​和 b i b_i bi​的前缀和，对于一个点查找 b i b_i bi​前缀和中比 a i a_i ai​大的数，这里因为是前缀和，所以自然就是有序的，可以直接二分。

    code：

    #include
#define LL long long
#define PB push_back
using namespace std;

struct edge
{
	LL next,vala,valb,from,to;
}e[201010];
LL head[201010],ans[201010];
LL n,tot = 0;

void add(LL u,LL v,LL a,LL b)
{
	tot++;
	e[tot].from = u;
	e[tot].to = v;
	e[tot].vala = a;
	e[tot].valb = b;
	e[tot].next = head[u];
	head[u] = tot;
}

vector<LL>sum;

inline void dfs(LL p,LL suma,LL sumb)
{
	sum.PB( sumb );
	LL pos = upper_bound( sum.begin() , sum.end() , suma ) - sum.begin();
	if( pos==0 )
	{
		ans[p] = 0; 
	}
	else 
	{
		ans[p] = pos-1;
	}
	for(int i=head[p];i!=-1;i=e[i].next)
	{
		LL v = e[i].to;
		dfs( v , suma+e[i].vala , sumb+e[i].valb );
	}
	sum.pop_back();
}

void solve()
{
	scanf("%lld",&n);
	LL p,a,b;
	for(int i=1;i<=n;i++) head[i] = -1;
	for(int i=2;i<=n;i++)
	{
		scanf("%lld %lld %lld",&p,&a,&b);
		add( p,i,a,b );
	}
	dfs(1,0,0);
	for(int i=2;i<=n;i++)
	{
		printf("%lld ",ans[i]);
	}
	printf("\n");
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	int t;
	cin>>t;
	while( t-- )
	solve();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
  • 相关阅读:
    SAP ABAP OData 服务如何支持 $filter (过滤)操作试读版
    号码吉凶查询易语言代码
    代码随想录训练营day58 || ● 739. 每日温度 ● 496.下一个更大元素 I
    springboot~自定义favicon加载问题
    【LSSVM回归预测】基于matlab人工蜂群算法优化最小二乘支持向量机LSSVM数据回归预测【含Matlab源码 2213期】
    【云原生之k8s】Pod 基础概念
    移动端阻止Touch导致的页面滑动/缩放
    308. 二维区域和检索 - 可变 线段树/哈希
    java进阶(七)------多线程---多线程操作同一变量
    区块链游戏解说：什么是 Ultimate Champions
  • 原文地址：https://blog.csdn.net/ojzha/article/details/126141997