A-Sorted Arrays
题意：
给你一个长度为n的数组，让你求最少能将这个数组分成多少个非递增或非递减的连续子串。
solution：
贪心
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int a[100005];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
bool flag;
int c=0;
int l=1,r=n;
while(l<=r)
{
if(a[l]>a[l-1])
{
c++;
while(a[l]>=a[l-1]&&l<=r)l++;
l++;
}
else if(a[l]<a[l-1])
{
c++;
while(a[l]<=a[l-1]&&l<=r)l++;
l++;
}
else
l++;
}
cout<<c<<endl;
return 0;
}
B-Hamiltonish Path
题意：
给你一个无向简单图，有n个点，m条边，m行点相连的情况。让你求一条简单路径。
简单路径要求如下：
这条路径要经过2个及以上的点
这条路径对于相同的点只能经过一次
路径上的点必须与端点有直接相连的边
solution：
比赛的时候想到了一个奇怪的方法（扩大路径法），找一个点，然后向两边延伸，使端点与路径上的所有点相连。也就是跑两次dfs即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
vector<int> e[100005];
int vis[100005];
stack<int> st,stt;
bool dfs(int u)
{
bool flag=true;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(vis[v])continue;
vis[v]=1;
st.push(v);
flag=false;
if(dfs(v))return true;
st.pop();
vis[v]=0;
}
if(flag)return true;
else return false;
}
bool dfss(int u)
{
bool flag=true;
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(vis[v])continue;
vis[v]=1;
stt.push(v);
flag=false;
if(dfss(v))return true;
stt.pop();
vis[v]=0;
}
if(flag)return true;
else return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int u,v;scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
vis[i]=1;
st.push(i);
if(dfs(i))
if(dfss(i))break;
while(!st.empty())
{
int x=st.top();st.pop();
vis[x]=0;
}
while(!stt.empty())
{
int x=stt.top();stt.pop();
vis[x]=0;
}
}
printf("%d\n",st.size()+stt.size());
while(!st.empty())
{
int x=st.top();st.pop();
printf("%d ",x);
}
int res[100005],cnt=0;
while(!stt.empty())
{
res[cnt++]=stt.top();stt.pop();
}
for(int i=cnt-1;i>=0;i--)
printf("%d ",res[i]);
return 0;
}
C-Ants on a Circle
D-Piling Up
E-Placing Squares
F-Two Faced Cards
G-Alice&Brown
题意：
给了你两堆石子，分别为x,y个，然后你可以从一堆石子里取2i个石子扔掉，并且往另一堆石子里放i个，取2i的条件是那对石子的个数大于等于2i
solution：
打表找规律，but我不会
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 300;
int dp[1005][1005];
int get(int x,int y)
{
if(x+y<=1)return 0;
if(x==1&&y==1)return 0;
if(x==0||y==0)return 1;
if(dp[x][y]!=-1)return dp[x][y];
for(int i=1;2*i<=x;i++)
{
if(get(x-2*i,y+i)==0)return dp[x][y]=1;
}
for(int i=1;2*i<=y;i++)
{
if(get(x+i,y-2*i)==0)return dp[x][y]=1;
}
return dp[x][y]=0;
}
int main()
{
/* memset(dp,-1,sizeof(dp)); for(int i=0;i<=10;i++) { for(int j=0;j<=10;j++)printf("%d ",get(i,j)); putchar('\n'); } */
ll x,y;
scanf("%lld%lld",&x,&y);
if(abs(x-y)<=1)printf("Brown\n");
else printf("Alice\n");
return 0;
}
H-Alice in linear land
I-Dam
J-Simple Knapsack
题意：
给了你n个物品的重量、价值，以及背包最多能装w，求背包所装东西的最大价值
solution：
贪心：
将物品按重量放在四个数组里，然后从大到小排序，暴力枚举解的情况
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,W;
int w1;
vector<int>e[10];
ll v[5],c[5];
ll maxn=0;
int main()
{
scanf("%d%d",&n,&W);
for(int i=0;i<n;i++)
{
int w,v;scanf("%d%d",&w,&v);
if(i==0)w1=w;
e[abs(w1-w)].push_back(v);
}
for(int i=0;i<4;i++)
sort(e[i].begin(),e[i].end());
ll sum=0;
for(int i=e[0].size();i>=0;i--)
{
if(i!=e[0].size())
v[0]+=e[0][i],c[0]++;
v[1]=0;c[1]=0;
sum=c[0]*w1+c[1]*(w1+1)+c[2]*(w1+2)+c[3]*(w1+3);
if(sum<=W)
maxn=max(maxn,v[0]+v[1]+v[2]+v[3]);
for(int j=e[1].size();j>=0;j--)
{
if(j!=e[1].size())
v[1]+=e[1][j],c[1]++;
v[2]=0;c[2]=0;
sum=c[0]*w1+c[1]*(w1+1)+c[2]*(w1+2)+c[3]*(w1+3);
if(sum<=W)
maxn=max(maxn,v[0]+v[1]+v[2]+v[3]);
for(int k=e[2].size();k>=0;k--)
{
if(k!=e[2].size())
v[2]+=e[2][k],c[2]++;
v[3]=0;c[3]=0;
sum=c[0]*w1+c[1]*(w1+1)+c[2]*(w1+2)+c[3]*(w1+3);
if(sum<=W)
maxn=max(maxn,v[0]+v[1]+v[2]+v[3]);
for(int q=e[3].size();q>=0;q--)
{
if(q!=e[3].size())
v[3]+=e[3][q],c[3]++;
sum=c[0]*w1+c[1]*(w1+1)+c[2]*(w1+2)+c[3]*(w1+3);
if(sum<=W)
maxn=max(maxn,v[0]+v[1]+v[2]+v[3]);
}
}
}
}
printf("%lld\n",maxn);
return 0;
}
dp：
应该可能是个二维dp吧，不是很懂。反正就是这样过的。把wi的值压缩一下
0,w1,w1+1,w1+2,w1+3,2w1,2w1+1,2w1+2,2w1+3,2w1+4,2w1+5,2w1+6…
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[105][400];
int maxn=0;
int n,W;
int w[105],v[105];
int main()
{
scanf("%d%d",&n,&W);
for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
for(int j=n;j>=0;j--)
{
for(int k=min(j*3,w[1]);k>=0;k--)
{
ll now=w[1]*j+k;
if(now>W)continue;
if(now-w[i]<0)continue;
int mod=(now-w[i])%w[1];
int ans=(now-w[i])/w[1];
if(mod>ans*3)continue;
dp[j][k]=max(dp[j][k],dp[ans][mod]+v[i]);
//cout<<v[i]<<endl;
//printf("w[%d]=%d v[%d]=%d dp[%d][%d]=%d\n",i,w[i],i,v[i],j,k,dp[j][k]);
maxn=max(dp[j][k],maxn);
}
}
}
printf("%d",maxn);
return 0;
}
京公网安备 11010502036488号