https://ac.nowcoder.com/acm/contest/4784
膜法记录
状压枚举暴力，数据很水过了。按理说不行。
#include<bits/stdc++.h>
using namespace std;
const int N=25;
const int M=1e5+10;
char s[N][M];
int main(void)
{
int t; scanf("%d",&t);
while(t--)
{
int n,m,a,b; cin>>n>>m>>a>>b;
int c[M]={0},temp[M]={0},flag=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>s[i][j];
if(s[i][j]=='*') c[j]++;
}
for(int i=0;i<(1<<n);i++)
{
int cnt=0;
for(int j=0;j<n;j++)
if(i>>j&1) cnt++;
if(cnt>a) continue;
memcpy(temp,c,sizeof c);
for(int j=0;j<n;j++)
{
if(i>>j&1)
{
for(int k=0;k<m;k++)
if(s[j][k]=='*') temp[k]--;
}
}
cnt=0;
for(int j=0;j<m;j++) if(temp[j]) cnt++;
if(cnt<=b)
{
flag=1;
break;
}
}
if(flag) puts("yes");
else puts("no");
}
return 0;
}
正解：
#include<bits/stdc++.h>
using namespace std;
const int N=25;
const int M=1e5*2+10;
char s[N][M];
int temp[M*10];
int main(void)
{
int t; scanf("%d",&t);
while(t--)
{
int n,m,a,b; scanf("%d%d%d%d",&n,&m,&a,&b);
for(int i=0;i<(1<<n);i++) temp[i]=0;
for(int i=0;i<n;i++) scanf("%s",s[i]);
for(int i=0;i<m;i++)
{
int now=0;
for(int j=0;j<n;j++) if(s[j][i]=='*') now|=(1<<j);
temp[now]++;
}
//temp[i]表示i状态下的个数
for(int i=0;i<n;i++)//枚举消灭的行
for(int j=0;j<(1<<n);j++)
if( (j&(1<<i))==0 ) //说明该行为消灭。
temp[j|(1<<i)]+=temp[j];
int flag=0;
for(int i=0;i<(1<<n);i++)
{
int cnt=0;
for(int j=0;j<n;j++)
{
if(i>>j&1) cnt++;
}
if(cnt<=a&&m-temp[i]<=b) flag=1;//temp[i]存的是已经消灭的行
}
if(flag) puts("yes");
else puts("no");
}
return 0;
}
阶乘【二分】
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long int LL;
vector< pair<int,int> >ve;
void solve(int x)
{
ve.clear();
for(int i=2;i<=x/i;i++)
{
int s=0;
while(x%i==0) x/=i,s++;
if(s) ve.push_back({i,s});
}
if(x!=1) ve.push_back({x,1});
}
bool check(int x)
{
for(int i=0;i<ve.size();i++)
{
int cnt=0,temp=x;
while(temp) cnt+=temp/ve[i].first,temp/=ve[i].first;
if(cnt<ve[i].second) return false;
}
return true;
}
int main(void)
{
int t; cin>>t;
while(t--)
{
int x; cin>>x;
solve(x);
LL l=1,r=1e9;
while(l<r)
{
LL mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<'\n';
}
return 0;
}
完全图【二分】
例如：n=5 那么依次减 4，3，2，1条边才能从1个连通块变成5个连通块。
二分找到边界即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long int LL;
template <typename T>
inline T read()
{
//声明 template 类, 要求提供输入的类型 T, 并以此类型定义内联函数 read()
T sum = 0, fl = 1; // 将 sum,fl 和 ch 以输入的类型定义
int ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
return sum * fl;
}
template <typename T>
inline void write(T x)
{
static int sta[35];
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) putchar(sta[--top] + 48); // 48 是 '0'
}
__int128 n,m;
bool check(__int128 x)
{
__int128 sum2=(n)*(n-1)/2;
__int128 sum1=x*(x+1)/2;
if(sum2-sum1<=m)
{
return true;
}
return false;
}
int main(void)
{
LL t; cin>>t;
while(t--)
{
n= read<__int128>();
m= read<__int128>();
__int128 l=0,r=n-1;
while(l<r)
{
__int128 mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
write((n-1-l)+1);
puts("");
}
return 0;
}
A+B问题【签到】
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N];
int main(void)
{
cin>>n;
cout<<4294967296;
return 0;
}
树上求和【思维 贪心】
贪心，就是先求出每条边用的次数。然后排序，次数多的先分配小的权值。
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=1e5+10;
vector<int>ve[N];
LL cnt[N],n;
void dfs(int u,int fa)
{
cnt[u]=1;
for(int i=0;i<ve[u].size();i++)
{
int j=ve[u][i];
if(j==fa) continue;
dfs(j,u);
cnt[u]+=cnt[j];
}
}
bool cmp(LL a,LL b){return a>b;}
int main(void)
{
cin>>n;
for(int i=1;i<=n-1;i++)
{
int a,b; cin>>a>>b;
ve[a].push_back(b);
ve[b].push_back(a);
}
dfs(1,-1);
vector<LL>ve;
for(int i=2;i<=n;i++) ve.push_back(cnt[i]*(n-cnt[i]));
sort(ve.begin(),ve.end(),cmp);
LL sum=0;
for(LL i=0,j=1;i<ve.size();i++,j++) sum+=ve[i]*j;
cout<<sum;
return 0;
}
奇怪的背包问题增加了【思维】
#include<bits/stdc++.h>
using namespace std;
const int N=1e5*5+10;
typedef long long int LL;
LL a[N],b[N];
int main(void)
{
int t; cin>>t;
while(t--)
{
int n; cin>>n;
int cnt[35]={0};
LL sum=0;
for(int i=0;i<n;i++)
cin>>a[i],b[i]=a[i];
sort(b,b+n);
sum=0;
for(int i=n-1;i>=0;i--)
{
if(sum+(1<<b[i])<=(1<<30))
sum+=(1<<b[i]),cnt[b[i]]++;
if(sum==(1<<30)) break;
}
if(sum==(1<<30))
{
for(int i=0;i<n;i++)
{
if(cnt[a[i]]) cout<<'1',cnt[a[i]]--;
else cout<<'0';
}
puts("");
}
else puts("impossible");
}
return 0;
}
寻找子串
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N];
int main(void)
{
string s; cin>>s;
vector<string>ve;
for(int i=0;i<s.size();i++)
for(int len=1;i+len<=s.size();len++)
ve.push_back(s.substr(i,len));
sort(ve.begin(),ve.end());
cout<<ve[ve.size()-1];
return 0;
}
最大的差
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N];
int main(void)
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
cout<<a[n-1]-a[0];
return 0;
}
