- chenshixian 的博客
陈室先的总结7.10day3
-
chenshixian
LV 2
@
2024-7-11 16:16:10
🚀️ 题目传送门
T1# 小田的01变换😄
😕 错的点
1.freopen!!!!!!!!!!!!!!!!写错了思路和其它代码都对,以后要认真仔细,不犯同样的错误
❤️ 思路
- cout<<0;全是 0 或 1 ，直接cout<< 0
- cout<<1 ;用
x, y统计0 和 1 的个数，如果不等于cout<<1; 。 - cout<<-1;在长度为2时两个元素分变为0,1那么cout<<-1;
- cout<<2;在长度不为2时，且0和1数量相同，那么cout<<2 (假如有一个如上述数组a(1~n),先1 ~ n-1,再1 ~n)
🎉️ 代码
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("change.in","r",stdin);
freopen("change.out","w",stdout);
int n,x=0,y=0;
cin>>n;
for(int i=1;i<=n;i++){
char a;
cin>>a;
if(a=='0')x++;
else y++;
}
if(n==1)cout<<0;
else if(n==2&&x==y)cout<<-1;
else if(x==y)cout<<2;
else if(x==n||y==n)cout<<0;
else if(x!=y)cout<<1;
}
T2小田滑雪😄 😄 😄
😕 错的点
1.没有想到思路，思维要加强，模拟找错能力也是
思路❤️
用di 表示到了全赛道的哪里， an ：过了多少时间。这里速度的分母是每次 **+**1 ，用一个 sp 记录分母，速度就是 1 / sp ，在一个 while 中每次更新当前位置近的距离，也就是失误时间对应的距离和当前失误距离来比较。
代码🎉️
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("snow.in","r",stdin);
freopen("snow.out","w",stdout);
vector<int> t,d;
int n;
cin>>n;
for(int i=1;i<=n;i++){
char s;
int a;
cin>>s;
cin>>a;
if(s=='T')t.push_back(a);
if(s=='D')d.push_back(a);
}
sort(t.begin(),t.end());
sort(d.begin(),d.end());
d.push_back(2e9);
t.push_back(2e9);
double an=0,di=0,v=1;
int i=0,j=0;
while(i<t.size()-1||j<d.size()-1){
double vi=1/v;
v++;
double tmp=di+(t[i]-an)*vi;
if(tmp<d[j]){
di=tmp;
an=t[i];
i++;
}
else{
an=an+(d[j]-di)/vi;
di=d[j];
j++;
}
}
an+=(1000-di)/(1.0/v);
cout<<(long long)(an+0.5);
}
T3 小田赶牛😄 😄
😕 错的地方
1.结构体排序的cmp推错了，要多打草稿，多算样例，这样才能推对
❤️ 思路
搜先要想到的是这是一道排序题，可以用结构体或pair来写，最难的是cmp,正确的写法是： return a.t*b.d<a.d*b.t; 然后还要用线性优化，如下 long long g=0; for(int i=1;i<=n;i++){k+=a[i].d*g; g+=2*a[i].t; }
代码🎉️
#include<bits/stdc++.h>
using namespace std;
struct P{
int t,d;
}a[100010];
int g[100010];
long long k;
bool cmp(P a,P b){
return a.t*b.d<a.d*b.t;
}
int main(){
freopen("cow.in","r",stdin);
freopen("cow.out","w",stdout);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].t>>a[i].d;
}
sort(a+1,a+1+n,cmp);
long long g=0;
for(int i=1;i<=n;i++){
k+=a[i].d*g;
g+=2*a[i].t;
}
cout<<k;
}
T4 拼接最大数😄 😄
错的地方😕
1.这道题是一个复杂的算法题，以后这种题要多练练，才能掌握
❤️ 思路
第一步：先将输入放入一个数组 第二步：枚举两个数组的长度 第三步：再获取字典序 第四步：按归并的思想去组合，注意等于是要按字典序来 第五步：输出
代码🎉️
#include<bits/stdc++.h>
using namespace std;
int c(vector<int>a,int da,vector<int>b,int db) {
int le1=a.size(),le2=b.size();
while(da<le1&&db<le2) {
if(a[da]!=b[db])return a[da]>b[db];
da++,db++;
}
if(da<le1)return 1;
else return 0;
}
vector<int>g(vector<int>a,int k){
int n=a.size();
if(n<=k)return a;
int t=n-k;
vector<int>st;
for(int i=0;i<n;i++) {
while(st.size()>0&&st.back()<a[i]&&t>0){
st.pop_back();
t--;
}
if(st.size()<k)st.push_back(a[i]);
else t--;
}
return st;
}
vector<int>ma(vector<int> a,vector<int> b) {
int le1=a.size(),le2=b.size();
vector<int>r;
int i=0,j=0;
while(i<le1&&j<le2) {
if(a[i]>b[j])r.push_back(a[i++]);
else if(a[i]<b[j]) r.push_back(b[j++]);
else{
if(c(a,i,b,j)>0)r.push_back(a[i++]);
else r.push_back(b[j++]);
}
}
while(i<le1)r.push_back(a[i++]);
while(j<le2)r.push_back(b[j++]);
return r;
}
int main(){
freopen("big.in","r",stdin);
freopen("big.out","w",stdout);
int n,m,k;
cin>>n>>m>>k;
vector<int>a,b;
for(int i=1;i<=n;i++) {
int x;
cin>>x;
a.push_back(x);
}
for(int i=1;i<=m;i++) {
int x;
cin>>x;
b.push_back(x);
}
vector<int>an(k,0);
for(int i=0;i<=k;i++) {
int le1=i,le2=k-i;
vector<int>t1=g(a,le1);
vector<int>t2=g(b,le2);
vector<int>r=ma(t1,t2);
if(r.size()==k&&c(r,0,an,0)>0)an=r;
}
for(auto x:an)cout<<x;
}
T5小W运水😄 😄 😄
😕 错的地方
图论用dfs写的，下次要用对代码，不能混用
❤️ 思路
用朴素的图论的模版，改一下起点和终点，以及浮点数，就可以写出来了
🎉️代码
#include <bits/stdc++.h>
using namespace std;
int g[2010][2010],n,m,s,h;
double di[2010];
bool st[2010];
void f(){
for(int i=1;i<=n;i++)di[i]=0x3f3f3f3f;
di[h]=100;
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||di[j]<di[t]))t=j;
}
st[t]=1;
for(int j=1;j<=n;j++){
if(g[t][j]<200&&di[t]/(1-g[t][j]*0.01)<di[j]){
di[j]=di[t]/(1-g[t][j]*0.01);
}
}
}
}
int main(){
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);
cin>>n>>m;
memset(g,0x3f,sizeof(g));
while(m--){
int x,y,z;
cin>>x>>y>>z;
g[x][y]=z,g[y][x]=z;
}
cin>>s>>h;
f();
printf("%.8lf",di[s]);
}
T6WOW😄 😄
错的地方😕
1.纯暴力，以后要有能推状态转移方程的能力，不能局限于暴力
❤️ 思路
本题可以用前后缀和 /DP
DP:
f[i][0]:是vv的数量
f[i][0]:是vvo的数量
f[i][0]:是vvovv的数量
状态转移方程为：
if(s[i]=='o')f1+=f0;
else if(s[i-1]=='v')f0++,f2+=f1;
🎉️ 代码
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("wow.in","r",stdin);
freopen("wow.out","w",stdout);
string s;
cin>>s;
long long f0,f1,f2;
f0=f1=f2=0;
for(int i=0;i<s.size();i++){
if(s[i]=='o')f1+=f0;
else if(s[i-1]=='v')f0++,f2+=f1;
}
cout<<f2;
}