题解：答案为$\lfloor \frac{a+b+c}{2} \rfloor$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
long long a,b,c,ans;
int q;
int main()
{
cin>>q;
while(q--)
{
cin>>a>>b>>c;
cout<<(a+b+c)/2<<endl;
}
return 0;
}
|
题意简述：
有T组数据 给出一个长度为$n$的序列 求 不能打乱顺序 将其分成$k$组 让每一组的和为奇数 如果不可能做到 输出“NO” 否则输出“YES” 第二行输出每块末尾的标号
题解：
首先需要知道：
奇数+偶数=奇数
奇数+奇数=偶数
偶数+偶数=偶数
所以要让一段和为奇数必定至少存在一个奇数 那么首先扫描一遍数组如果奇数个数小于$k$那么直接输出无解 如果大于$k$的话可以将奇数两两合并变成偶数 所以如果剩下奇数个奇数则输出无解 输出答案时先输入前$k-1$个奇数的位置，最后输出$n$即可
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
|
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=200050;
int q,a[maxn],n,k,num;
int main()
{
cin>>q;
while(q--)
{
num=0;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]&1) num++;
}
if(num<k||(num-k)&1) puts("NO");
else
{
puts("YES");
int temp=0,t=1;
while(temp<k-1)
{
if(a[t]&1)
{
printf("%d ",t);
temp++;
}
t++;
//cout<<"----"<<t<<endl;
}
printf("%d\n",n);
}
}
return 0;
}
|
题意简述：
有$n$个机器人在一个平面上 第$i$个机器人的位置是$(X_i,Y_i)$
在设计的时候 第$i$个机器人可以执行的操作：
1.位置从$(X_i,Y_i)$变为$(X_i-1,Y_i)$
2.位置从$(X_i,Y_i)$变为$(X_i,Y_i+1)$
3.位置从$(X_i,Y_i)$变为$(X_i+1,Y_i)$
4.位置从$(X_i,Y_i)$变为$(X_i,Y_i-1)$
但设计出现了缺陷，某些机器人可能不能执行上述的某些操作
你需要找一个点$(A,H)$使得$n$个机器人都可以到达$(A,H)$ 注意 一开始的位置在 $(A,H)$也算到达 且对于$A,H$的范围有限制$-10^5\leq A,H \leq 10^5$
题解：
对于操作1机器人如果禁用那它的横坐标一定大于等于$X_i$ 剩余操作同理
那么我们就可以维护$maxx$,$maxy$,$minx$,$miny$ 若出现矛盾则无解 否则随便输出限制内的点即可
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
|
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int q,n;
int main()
{
cin>>q;
while(q--)
{
cin>>n;
int maxx=1e5,minx=-1e5,maxy=1e5,miny=-1e5;
for(int i=1;i<=n;i++)
{
int x,y,t1,t2,t3,t4;
cin>>x>>y>>t1>>t2>>t3>>t4;
if(!t1) minx=max(minx,x);
if(!t2) maxy=min(maxy,y);
if(!t3) maxx=min(maxx,x);
if(!t4) miny=max(miny,y);
}
if(minx>maxx||miny>maxy) puts("0");
else cout<<1<<" "<<minx<<" "<<miny<<endl;
}
return 0;
}
|
题意简述：
给定一个只包含R,G,B三个字母的长度为$n$的字符串 修改其中的字母使得该字符串中存在一个长度为$k$的子串同时是"RGBRGBRGB..."无限长度串的子串
题解：
首先考虑暴力做法 以字符串每个点都作为开头暴力枚举后$k$个 分别计算变为RGB,GBR,BRG三种形式的代价 然后取最小值
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
|
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=2010;
int q,n,k,a[maxn];
int main()
{
cin>>q;
while(q--)
{
memset(a,0,sizeof(a));
cin>>n>>k;
string s;cin>>s;
for(int i=0;i<s.size();i++)
{
if(s[i]=='R') a[i+1]=0;
if(s[i]=='G') a[i+1]=1;
if(s[i]=='B') a[i+1]=2;
}
int ans=k;
for(int i=1;i<=n-k+1;i++)
{
int x=0,y=0,z=0;
for(int j=0;j<k;j++)
{
if(a[i+j]!=j%3) x++;
if(a[i+j]!=(j+1)%3) y++;
if(a[i+j]!=(j+2)%3) z++;
}
ans=min(min(ans,x),min(y,z));
}
cout<<ans<<endl;
}
return 0;
}
|
之后我们可以考虑用前缀和来优化 由于只有可能是三种模式 所以我们维护一个$f[i][j]$表示对于第$i$个模式处理到$j$需要多少代价 之后分别计算$f[i][j]-f[i][j-k]$即可
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
|
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=200050;
int q,n,k,f[3][maxn];
string s,a="RGB";
int main()
{
//ios::sync_with_stdio(false);
scanf("%d",&q);
while(q--)
{
f[0][0]=f[1][0]=f[2][0]=0;
scanf("%d%d",&n,&k);
cin>>s;
for(int i=0;i<3;i++)
{
for(int j=1;j<=n;j++)
{
if(s[j-1]!=a[(j+i-1)%3]) f[i][j]=f[i][j-1]+1;
else f[i][j]=f[i][j-1];
}
}
int ans=k;
for(int i=0;i<3;i++)
for(int j=k;j<=n;j++)
ans=min(ans,f[i][j]-f[i][j-k]);
printf("%d\n",ans);
}
return 0;
}
|
构造题 日后再补
题意简述：
给定一个无向带权连通图 求子节点两两之间路径从小到大排序之后第$k$长的路径长度
题解：
首先可以发现只有排序后前$k$条边是有用的 因为最坏情况下也只需要第$k$条边 而$k$又格外的小 所以就可以把$k$条边拉出来单独建图 之后有两种做法 一种直接跑$floyd$ 还有一种更优秀的是对于每个点都跑一边$dijkstra$
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
|
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
#define p pair<ll,ll>
#define ll long long
using namespace std;
const int maxn=200050;
ll n,m,k,ans;
ll head[maxn],num=0,cnt[maxn],dis[maxn],vis[maxn],pan[maxn],tot=0;
priority_queue<p,vector<p>,greater<p> > q;
vector<ll> res;
inline int read()
{
int x=0,t=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*t;
}
struct temp{
ll u,v,w;
bool operator<(const temp&a) const
{
return w<a.w;
}
}t[maxn];
struct node{
ll v,w,nex;
}e[maxn];
void add(int u,int v,int w)
{
e[++num].v=v;
e[num].w=w;
e[num].nex=head[u];
head[u]=num;
}
void dij(int s)
{
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
int u=q.top().second;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push(make_pair(dis[v],v));
}
}
}
}
int main()
{
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++)
{
int x,y,z;x=read(),y=read(),z=read();
t[i].u=x,t[i].v=y,t[i].w=z;
}
sort(t+1,t+m+1);
for(int i=1;i<=k;i++)
{
int u=t[i].u,v=t[i].v,w=t[i].w;
add(u,v,w);
add(v,u,w);
if(!pan[u]) cnt[++tot]=u,pan[u]=1;
if(!pan[v]) cnt[++tot]=v,pan[v]=1;
}
for(int i=1;i<=tot;i++)
{
dij(cnt[i]);
for(int j=i+1;j<=tot;j++) res.push_back(dis[cnt[j]]);
}
sort(res.begin(),res.end());
ans=res[k-1];
cout<<ans<<endl;
return 0;
}
|