1.被污染的支票
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int>L;
map<int,int>mp;
bool ok=0;
int num;
for(int i=1;i<=n;i++)
{
cin>>num;
if(mp[num]==1)ok=1;
else
{
mp[num]=1;
L.push_back(num);
}
}
sort(L.begin(),L.end());
int x=L.back()*2;//?????
vector<int>L2;
for(int i=2;i<x;i++)
{
if(x%i==0)L2.push_back(i);
}
if(L!=L2)ok=1;
if(ok)
{
cout<<-1<<endl;
}
else
{
cout<<x<<endl;
}
return 0;
}2.日期统计
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
int ans=0;
int num[100]={5, 6, 8, 6, 9, 1, 6, 1, 2, 4,
9, 1, 9, 8, 2, 3, 6, 4, 7, 7,
5, 9, 5, 0, 3, 8, 7, 5, 8, 1,
5, 8, 6, 1, 8, 3, 0, 3, 7, 9,
2, 7, 0, 5, 8, 8, 5, 7, 0, 9,
9, 1, 9, 4, 4, 6, 8, 6, 3, 3,
8, 5, 1, 6, 3, 4, 6, 7, 0, 7,
8, 2, 7, 6, 8, 9, 5, 6, 5, 6,
1, 4, 0, 1, 0, 0, 9, 4, 8, 0,
9, 1, 2, 8, 5, 0, 2, 5, 3, 3};
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
for(int mon=1;mon<=12;mon++)
{
for(int day=1;day<=days[mon];day++)
{
int temp[8]={2,0,2,3,mon/10,mon%10,day/10,day%10};
int k=0;
for(int i=0;i<100;i++)
{
if(num[i]==temp[k])
{
k++;
}
if(k==8)
{
ans++;
break;
}
}
}
}
cout<<ans<<endl;
return 0;
}3.01串的熵
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n=23333333;
for(int i=0;i<=n/2;i++)//0的次数
{
double a=(i*1.0)/n;
double b=((n-i)*1.0)/n;
double ans=0;
ans-=(a*log2(a)*i+b*log2(b)*(n-i));
if(fabs(ans-11625907.5798)<0.0001)
{
cout<<i<<endl;
break;
}
}
return 0;
}（注意浮点数，double，以及比较大小时使用1e-4）
4.冶炼金属
#include <iostream>
using namespace std;
#define ll long long
int main()
{
ll n,a,b,minn,maxx;
maxx=1e9;//要满足最小的
minn=0;//要满足最大的
cin>>n;
for(ll i=0;i<n;i++)
{
cin>>a>>b;
minn=max(minn,a/(b+1)+1);
maxx=min(maxx,a/b);
}
cout<<minn<<" "<<maxx;
return 0;
}//二分
#include <iostream>
using namespace std;
int a[10000+5];
int v[10000+5];
int n;
bool check_min(int x)
{
for(int i=1;i<=n;i++)
{
if(a[i]/x>v[i])return false;
}
return true;
}
bool check_max(int x)
{
for(int i=1;i<=n;i++)
{
if(a[i]/x<v[i])return false;
}
return true;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>v[i];
}
int L=1,R=1000000000,minn=0;
while(L<=R)
{
int mid=(L+R)>>1;
if(check_min(mid))
{
minn=mid;
R=mid-1;
}
else L=mid+1;
}
int maxx=0;
L=1,R=1000000000;
while(L<=R)
{
int mid=(L+R)>>1;
if(check_max(mid))
{
maxx=mid;
L=mid+1;
}
else R=mid-1;
}
cout<<minn<<" "<<maxx<<endl;
return 0;
}5.飞机降落
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node
{
int t,d,l;
};
bool ok=0;
vector<node>v;
vector<int>vis;
int n;
void dfs(int ***t,int last)
{
if(***t==n)
{
ok=1;
return;
}
for(int i=0;i<n;i++)
{
if(!vis[i]&&v[i].t+v[i].d>=last)//可以降落
{
vis[i]=1;
dfs(***t+1,max(last,v[i].t)+v[i].l);
vis[i]=0;//恢复
}
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n;
v.clear();
vis.clear();
for(int i=1;i<=n;i++)
{
//t d l (t/t+d -- l)
int x,y,z;
cin>>x>>y>>z;
v.push_back({x,y,z});
vis.push_back(0);
}
ok=0;
dfs(0,0);//0架飞机，0需要时间
if(!ok)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}6.接龙数列
这道题其实本质就是求解出数列中最长的接龙数列，计算出最长的接龙数列长度，数列总长度-最长接龙数列长度等于最少删除次数。这就是一个求最优解的问题，然而看到这道题的数据量可以发现，暴力求解一定会超时，因此考虑动态规划。 动态规划最重要的就是状态转移方程，而这个题目就可以定义状态为当前最长接龙数列长度，则dp[i]就是以i为数字最后一位的最长接龙数列长度，设x为当前数字的第一位(如果为接龙数列，也就是前一位数的最后一位)，y为当前数字的最后一位，则转移方程可以写为dp[y]=max(dp[x]+1,dp[y])
#include <iostream>
using namespace std;
int f[10];//表示在i=0-9中,f[i]为以i数字为连接的最长接龙数列的长度
int main()
{
int n;
cin>>n;
int ans=0;
string s;
for(int i=0;i<n;i++)
{
cin>>s;
int pre=s[0]-'0',nex=s[s.size()-1]-'0';
f[nex]=max(f[nex],f[pre]+1);
ans=max(ans,f[nex]);
}
cout<<n-ans<<endl;//总的-最长长度=删去的
return 0;
}7.岛屿个数
搜索出所有岛屿，这个不难做到。由于岛屿之间互相隔离，则如果岛屿的一个格子在一个环内，那么整个岛屿也都在环内。遍历所有的岛屿，选中当前岛屿的第一个格子，搜索周围海洋，若能搜索到地图的边界外，则此岛屿不在任何一个环内；否则，此岛屿在某个环内，岛屿数量减一。
#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
#define pii pair<int,int>
const int N=100;
int n,m,ans;
vector<vector<bool>>vis;
string s[N];
int dx[8]={-1,1,0,0,-1,1,-1,1};
int dy[8]={0,0,-1,1,-1,1,1,-1};
bool inmap(int x,int y)
{
if(x<1||x>n||y<1||y>m)return 0;
return 1;
}
//bfs统计岛屿的情况
void bfs(int x,int y)
{
vis[x][y]=1;
queue<pii>q;
q.push({x,y});
while(!q.empty())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int xx=t.first+dx[i];
int yy=t.second+dy[i];
if(!inmap(xx,yy)||vis[xx][yy]||s[xx][yy]!='1')continue;
vis[xx][yy]=1;
q.push({xx,yy});
}
}
}
bool check(int x,int y)//是否不在环内，即周围是海洋（用是否到边界判断）
{
vector<vector<bool>>fin(n+1,vector<bool>(m+1,0));
fin[x][y]=1;
queue<pii>q;
q.push({x,y});
while(!q.empty())
{
auto t=q.front();
q.pop();
//到达边界，证明不在环中
if(t.first==1||t.first==n||t.second==1||t.second==m)return 1;
for(int i=0;i<8;i++)
{
int xx=t.first+dx[i];
int yy=t.second+dy[i];
if(!inmap[xx][yy]||fin[xx][yy]||s[xx][yy]!='0')continue;
fin[xx][yy]=1;
q.push({xx,yy});
}
}
return 0;
}
int main()
{
int t;
cin>>t;
while(t--)
{
ans=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]='2'+s[i];
}
vis=vector<vector<bool>>(n+1,vector<bool>(m+1,0));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!vis[i][j]&&s[i][j]=='1')
{
bfs(i,j);
if(check(i,j))ans++;
}
}
}
cout<<ans<<endl;
}
return 0;
}8.子串简写
#include <iostream>
using namespace std;
int main()
{
int k;
//最小可以简写的长度
cin>>k;
string s;
char st,ed;
cin>>s>>st>>ed;
long long ans=0;
int st_num=0;
for(int i=0,j=k-1;j<s.size();i++,j++)
{
if(s[i]==st)st_num++;
if(s[j]==ed)ans+=st_num;
}
cout<<ans<<endl;
return 0;
}
//4
//abababdb a b（注意规律，开long long）
9.整数删除
#include<bits/stdc++.h>
using namespace std;
//优先队列+双向链表
const int N=5e5+10;
#define ll long long
#define val first
#define pos second
#define pli pair<ll,int>
int n,k;
ll a[N],pre[N],nxt[N];
priority_queue<pli,vector<pli>,greater<pli>>q;//小根堆
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
q.push({a[i],i});
pre[i]=i-1;
nxt[i]=i+1;
}
pre[1]=-1;
nxt[n]=-1;
while(k--)
{
pli now;
do{
now=q.top();
q.pop();
}while(a[now.pos]!=now.val);//保证弹出同一个
int PRE=pre[now.pos];
int NXT=nxt[now.pos];
if(PRE!=-1)
{
a[PRE]+=now.val;
q.push({a[PRE],PRE});
nxt[PRE]=NXT;
}
if(NXT!=-1)
{
a[NXT]+=now.val;
q.push({a[NXT],NXT});
pre[NXT]=PRE;
}
a[now.pos]=-1;
}
for(int i=1;i<=n;i++)
{
if(a[i]!=-1)cout<<a[i]<<" ";
}
return 0;
}10.景区导游
//最近公共祖先。倍增做法 (深搜)
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
const int N=1e5+10;
vector<int>e[N],w[N];
int n,k;
ll dep[N],fa[N][20],dist[N],b[N];
void dfs(int u,int father){
fa[u][0]=father;
dep[u]=dep[father]+1;
for(int i=1;i<20;i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
int t=w[u][i];
if(v!=father){
dist[v]=dist[u]+t;
dfs(v,u);
}
}
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;i>=0;i--){
if(dep[fa[u][i]]>=dep[v])
u=fa[u][i];
}
if(u==v) return v;
for(int i=19;i>=0;i--){
if(fa[u][i]!=fa[v][i]){
u=fa[u][i],v=fa[v][i];
}
}
return fa[u][0];
}
ll sol(int x,int y){
if(!x||!y) return 0;
return dist[x]+dist[y]-2*dist[lca(x,y)];
}
int main(){
cin>>n>>k;
for(int i=1;i<n;i++){
int x,y,t;
cin>>x>>y>>t;
e[x].push_back(y);
e[y].push_back(x);
w[x].push_back(t);
w[y].push_back(t);
}
dfs(1,0);
ll Dis=0;
for(int i=1;i<=k;i++){
cin>>b[i];
Dis+=sol(b[i],b[i-1]);
}
for(int i=1;i<=k;i++){
cout<<Dis-sol(b[i-1],b[i])-sol(b[i],b[i+1])+sol(b[i-1],b[i+1])<<" ";
}
return 0;
}11.砍树
#include <iostream>
#include <vector>
using namespace std;
const int N=1e5+10;
vector<int>e[N],num[N];
int n,m,dep[N],fa[N][21],s[N],ans;
void dfs(int u,int Fa)
{
dep[u]=dep[Fa]+1;
fa[u][0]=Fa;
for(int i=1;i<=20;i++)
{
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(auto &v:e[u])
{
if(v==Fa)continue;
dfs(v,u);
}
}
int LCA(int u,int v)
{
if(dep[u]<dep[v])swap(u,v);
for(int i=20;i>=0;i--)
{
if(dep[fa[u][i]]>=dep[v])
{
u=fa[u][i];
}
}
if(u==v)return u;
for(int i=20;i>=0;i--)
{
if(fa[u][i]!=fa[v][i])
{
u=fa[u][i];
v=fa[v][i];
}
}
return fa[u][0];
}
void dfs2(int u,int Fa)
{
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i],p=num[u][i];
if(v==Fa)continue;
dfs2(v,u);
s[u]+=s[v];
if(s[v]==m)ans=max(ans,p);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
num[x].push_back(i);
num[y].push_back(i);
}
dfs(1,0);
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
s[a]++;s[b]++;s[LCA(a,b)]-=2;
}
dfs2(1,0);
cout<<ans;
return 0;
}
