https://ac.nowcoder.com/acm/contest/11226/B
就是开桶思想。
回答：如何匹配
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9+5;
const int maxn=2e6+10;
const int MOD=998244353;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
//就是暴力
//回去在简单想想。没问题就可以过了。--感觉不需要记录。。
int n,m,col[202][202];
int b[202];
int main() {
int t;s
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(ll i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&col[i][j]);
}
}
for(int j=1;j<=m;j++) scanf("%d",&b[j]);
int ans=0;
int fd[202]={0};
for(int k=1;k<=m;k++){
fd[b[k]]=1;
ans=0;
for(int i=1;i<=n;i++){
int ok=0;
for(int j=1;j<=m;j++){
if(fd[col[i][j]]) ok++;
}
if(ok==k)
ans++;
}
printf("%d ",ans);
}
printf("\n");
}
}
- 错误票据
- 买不到的数目
- 树的直径核心代码
- 双指针
//=================================================分割线 - 理解，灵活运用他的概率dp
- 最小路+分块
- 不进位加法，减法
- dp理解1
- dp理解2
- 课间冷静分析题
7.数位dp很多没想明白
双指针
双指针可以对应坐标轴、下标来进行。—l，r可以是作为从1~n的数组坐标，也可以是1-n的下标。–这个格局要打开。
指针也不是唯一固定。l=0，r=0；----l=0，r=n-1; -----l=n-1,r=n-1;
一般 l<=r必有。防止左指针超过右指针。因为l==r代表就一个数所以是l<=r是合法的。
r < n必有。 否则就越界了。
r必有，满足条件继续走。
if(l>=n or 条件) break; 必有，当l>=n时，代表整个序列都跑完了。
l;
int l=0,r=0;
while(1)
{
while(l<=r&&条件&&r<n)
{
XXX
r++;
}
if(l>=n or 条件) break; //相当于第一层for循环的结束语句
XXX
l++;
}
错误票据
sstream的适用
string line,str;
getline(cin,line);
istringstream is(line)
while(is>>str)
买不到的数目
dfs如何枚举
bool dfs(int m,int p,int q)
{
if(m == 0) return true;
if(m >= p && dfs(m - p,p,q)) return true;
if(m >= q && dfs(m - q,p,q)) return true;
return false;
}
树的直径核心代码
ll dfs(int u,int fa)
{
ll dis =0;
ll d1=0,d2=0;
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue ;
ll d=dfs(v,u)+e[i].w;
dis=max(dis,d);
if(d>d1) d2=d1,d1=d;
else if(d>d2) d2=d;
}
ans=max(ans,d1+d2);
return dis;
}
//=================================================分割线
数位dp很多没想明白
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+9;
int dp[63][1<<12];
long long R[12];
int n;
int dfs(int p,int limit){
//cout<<p<<" "<<limit<<endl;
if(p<0) return 1;
if(dp[p][limit]!=-1) return dp[p][limit];
int ans=0;//用来记录第P位上有1的R[i],用于后续的限制解除.
for(int i=1;i<=n;i++)
if(R[i]&((long long)1<<p))//((long long)1<<p) 指点这一位. 如果r[i]的这个位置为1,则
ans|=(1<<i);//------ 00000000000. 哪些地方是1,就在那个位置标1. 0001000000类似这样.1都确定后,0是为所欲为的.
long long res=0;
res+=dfs(p-1,ans|limit);//如果第P位取0，所有ans记录的Ri全部解除限制ans｜limit。
for(int i=1;i<=n;i++){
if(((long long)1<<i)&limit)//取1的时候，如果Ri已经无限制了，保持无限制，其他这一位上有1的也为无限制。当然之前就已经无限制的数字在之后依旧无限制
res+=dfs(p-1,ans|limit);//----难理解.
else if(!((1<<i)&limit)&&ans&(1<<i))//R[I]被限制了，但这一位上有1，那么R[I]依旧保持限制，其他这一位上有1的变为无限制
res+=dfs(p-1,(ans^(1<<i))|(limit));//----难理解.
}
dp[p][limit]=res%mod;
return dp[p][limit];
}
int main(){
memset(dp,-1,sizeof(dp));
cin>>n;
for(int i=1;i<=n;i++){
scanf("%lld",&R[i]);
}
dfs(61,0);
cout<<dp[61][0]<<endl;
return 0;
}
课间冷静分析题
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int a[2]={};
string n;
cin>>n;
for(int i=0;i<(int)n.length();i++)
a[i&1]=a[i&1]*10+(n[i]-'0');
cout<<a[0]*a[1]+a[0]+a[1]-1<<endl;
}
return 0;
}
dp理解2
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=500+10;
const ll MOD= 1e9+7;
ll n,t,x,m;
char s[200010];
ll dp[200010][4];
int main()
{
cin>>n>>(s+1);
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
//当前状态由上一个状态转移
for(int j=0;j<=3;j++)
{
dp[i][j]=dp[i-1][j];
}
if(s[i]=='a') dp[i][1]=(dp[i-1][1]+dp[i][0])%MOD;
if(s[i]=='b') dp[i][2]=(dp[i-1][2]+dp[i][1])%MOD;
if(s[i]=='c') dp[i][3]=(dp[i-1][3]+dp[i][2])%MOD;
if(s[i]=='?')
{
dp[i][0]=(dp[i-1][0]*3)%MOD;
for(int j=1;j<=3;j++) dp[i][j]=(dp[i-1][j]*3)%MOD+(dp[i-1][j-1]%MOD)%MOD;
}
}
printf("%lld\n",dp[n][3]%MOD);
//system("pause");
return 0;
}
dp理解1
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=500+10;
const ll MOD= 998244353;
ll dp[maxn][maxn];
char op[maxn];
int a[maxn];
int sum[maxn];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
getchar();
scanf("%c",&op[i]);
if(op[i]=='+') {scanf("%d",&a[i]);}
sum[i]=sum[i-1]+(op[i]=='+');
}
ll ans=0;
for(int x=1;x<=n;x++)
{
if(op[x]=='-') continue;//只选择'+'
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=sum[i];j++)//它在1位置的时候，在2位置时候在。。。，前面操作是‘+’的个数sum[i]
{
if(x!=i) dp[i][j]=dp[i-1][j];//这里。x是+操作
if(op[i]=='-')
{
if(i<x)
{
if(j==0)
{
dp[i][j]=(dp[i][j]+dp[i-1][j]+dp[i-1][j+1])%MOD;//可能本来就是0，也有可能是1变成了。
}
else
{
dp[i][j]=(dp[i][j]+dp[i-1][j+1])%MOD;
}
}
else
{
//if(j==0) 还是不等0 都是下面这个转移方程所以就不写判断了。
dp[i][j]=(dp[i][j]+dp[i-1][j+1])%MOD;
}
}
else//对于'+'
{
if(a[i]<a[x]||a[i]==a[x]&&i<x)
{
dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD;
}
else
{
dp[i][j]=(dp[i][j]+dp[i-1][j])%MOD;
}
}
}
}
for(int i=0;i<=10;i++)
{
for(int j=0;j<=10;j++)
{
printf("%d ",dp[i][j]);
}
puts("");
}
puts("");
for(int j=0;j<=sum[n];j++) ans=(ans+dp[n][j]*a[x])%MOD;
}
printf("%lld\n",ans);
system("pause");
return 0;
}
/*
想法：
我认为的题目：求每种操作后的值。---组合数，
0是没有贡献的。所以我们需要的是有贡献的子序列
但什么时候能代表子序列有贡献？ 在ax下，有值。
1.必须包含第x次操作。（+ ax）
2，设s是集合T种小于ax的元素个数，则保证在每次-操作前，都s必须大于0.
----需要练习，怎么看出是dp----两个未知量的所有情况----所以很像dp。
有多少个满足这些操作的子序列？
设dp[i][j]表示有多少种满足上述条件的子序列。i：表示最后一次操作不晚于i(若i < x则不要求满足第一个条件
j:表示集合T拥有j个小于ax的元素。
dp====从哪边转移过来
*/
不进位加法，减法
int addk(int a,int b)
{
int base,aw,bw,ret=0;
for(base=1;base<=max(a,b);base*=k)
{
aw=a/base%k;//假设k为10. 其实就是把每位数单独拉出来，相加，取尾，乘位数
bw=b/base%k;
ret+=(aw+bw)%k*base;
例：（125 +66=181 拆成 (1+0)%10*100 + (2+6)%10*10+(5+6)%10*1=181）
}
return ret;
}
int subk(int a,int b)
{
int base,aw,bw,ret=0;
for(base=1;base<=max(a,b);base*=k)
{
aw=a/base%k;
bw=b/base%k;
ret+=(aw-bw+k)%k*base;
}
return ret;
}
最小路+分块
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e18;
const int maxn=5e5+10;
int t,n,m,q;
struct matrix
{
ll room[60][60];
matrix()
{
for(int i=0;i<60;i++)
for(int j=0;j<60;j++)
room[i][j]=INF;
};
friend matrix operator*(const matrix &a,const matrix &b)
{
matrix box;
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
box.room[i][j]=min(box.room[i][j],a.room[i][k]+b.room[k][j]);
}
}
}
return box;
}
};
matrix mat,box[110],matrix100[110];
void init(){
box[1]=mat;
for (int i=2;i<=101;i++) box[i]=box[i-1]*box[1];//分块前100
matrix100[1]=box[100];
for (int i=2;i<=101;i++) matrix100[i]=matrix100[i-1]*matrix100[1];//分块200 300 400...
for (int k=99;k>=1;k--){
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
box[k].room[i][j]=min(box[k].room[i][j],box[k+1].room[i][j]);
matrix100[k].room[i][j]=min(matrix100[k].room[i][j],matrix100[k+1].room[i][j]);
}
}
}
box[0]=box[1];
for (int i=0;i<55;i++){
for (int j=0;j<55;j++){
matrix100[0].room[i][j]=INF;
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
for(int i=0;i<60;i++)
for(int j=0;j<60;j++)
mat.room[i][j]=INF;
for(int i=1;i<=m;i++)
{
int u,v;
ll w;
scanf("%d %d %lld",&u,&v,&w);
mat.room[u][v]=min(mat.room[u][v],w);//??
}
init();
scanf("%d",&q);
while(q--)
{
int s,t,k;
scanf("%d %d %d",&s,&t,&k);
ll ans=INF;
ll x=k/100;
ll y=k%100;
for (int i=1;i<=n;i++){
ans=min(ans,matrix100[x].room[s][i]+box[y].room[i][t]);
ans=min(ans,matrix100[x+1].room[s][i]+box[0].room[i][t]);
}
if (x==0) ans=min(ans,box[y].room[s][t]);
if (y==0) ans=min(ans,matrix100[x].room[s][t]);
if (ans==INF) printf("-1\n");
else printf("%lld\n",ans);
}
}
system("pause");
return 0;
}
理解，灵活运用他的概率dp
题目
根据题目意思：求最大价值，且保证失败率在给定的范围内。
我们不妨换个思想，把失败率，转成 成功率，这样问题也会变的简单一点。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
const int INF = 0x3f3f3f3f;
const int maxn=10000+10;
using namespace std;
int t,m,n;
double p,dp[maxn],w[maxn];//w[i]表示第i件成功的概率， dp[i]表示价值为i时，成功的概率
int v[maxn];
int sum;//最大价值。
int main()
{
cin>>t;
while(t--)
{
sum=0;
scanf("%lf %d",&p,&n);
for(int i=1;i<=n;i++)
{
scanf("%d %lf",&v[i],&w[i]);
w[i]=1-w[i];
sum+=v[i];
}
memset(dp,0,sizeof(dp));
dp[0]=1;//
for(int i=1;i<=n;i++)
{
for(int j=sum;j>=v[i];j--)
{
dp[j]=max(dp[j],dp[j-v[i]]*w[i]);
}
}
for(int i=sum;i>=0;i--)
{
if(dp[i]>=1-p)
{
printf("%d\n",i);
break;
}
}
}
return 0;
}
http://acm.hdu.edu.cn/showproblem.php?pid=4460
广搜题目，hdu朋友链。
#include<iostream>
using namespace std;
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<string.h>
int n;
int step[1011],vis[1011];
vector<int> fre[1011];
int maxans=-1;
int bfs(int i)
{
memset(step,0,sizeof(step));
memset(vis,0,sizeof(vis));
queue<int>q;
q.push(i);
set<int>l; //判断7步之内能否reach到所有人 ？？？？？？？？？
l.insert(i); //？？？
int f,maxs=-1;
vis[i]=1;
//=======================================开始队列。
while(!q.empty())
{
f=q.front();
maxans=max(maxans,step[f]);
if(l.size()==n)//?????
return 1;
if(step[f]>6)
break;
for(int j=0;j<fre[f].size();j++)
{
if(!vis[fre[f][j]]&&step[f]<6)
{
int k=fre[f][j];
vis[k]=1;
step[k]=step[f]+1;
q.push(k);
l.insert(k);
maxans=max(maxans,step[k]);
}
}
q.pop();
}
if(l.size()==n) return 1;
return 0;
}
int main()
{
ios::sync_with_stdio(false);//加快cin读取速度，不然tle
while(cin>>n &&n)
{
//=======================================初始化。
for(int i=1;i<=n;i++) fre[i].clear();//clear？？ 初始化吧。
string s1,s2;
map<string,int> nd; //用map把字符串转化为对应序号
//=======================================输入人物
for(int i=1;i<=n;i++)
{
cin>>s1;
nd[s1]=i;
}
//=======================================输入关系。
int m;cin>>m;
for(int i=1;i<=m;i++)
{
cin>>s1>>s2;
int j1=nd[s1],j2=nd[s2];
fre[j1].push_back(j2);//?????
fre[j2].push_back(j1);
}
//=======================================分别对每个点进行广搜。如果发现有有个点是被孤立的，标志，退出。
int fg=0;
for(int i=1;i<=n;i++)
{
if(!bfs(i))
{
cout<<"-1"<<endl;fg=1; break;
}
}
if(!fg)
cout<<maxans<<endl;
}
return 0;
}
/*
了解 clear的作用。
*/
字符串 判断能否拆成降序。
class Solution {
public:
bool splitString(string s)
{
int n=s.size();
for(int i=1;i<1<<n-1;i++)//这种特定写法注意。
{
bool f=true;
unsigned long long last=-1,x=s[0]-'0';
for(int j=0;j<n-1;j++)
{
if(i>>j&1)//学习。每怎么搞懂。----看看第j位 是不是1 即是不是分割。
{
if(last!=-1&&x!=last-1)
{
f=false;
break;
}
last=x;
x=s[j+1]-'0';
}
else
{
x=x*10+s[j+1]-'0';
}
}
if(x!=last-1) f=false;//最后一次还要单独判断一次。
if(f) return true;
}
return false;
}
};
clear()就是清空容器的作用