E.A+B问题：
有符合整数将最高位作为符号位，其真值仍然是一个 的整数，也就是模
意义下的非负整数。所以，无论
为多少，枚举
，多有相应的
。（模
下进行）。所以，答案始终为
。
I.寻找子串：
分析：
找出字典序最大的字母所在的位置，如何比较以它们为首的字符串，确定起点，因为终点一定是原字符串的末尾。
一开始没有意识到结尾是确定的，还去找结尾的位置，该好好反思啊。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define fy first
#define sd second
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int N=1010;
char ss[N],s1[N];
int p[N];
int main()
{
scanf("%s",ss+1);
int cnt=0,n=strlen(ss+1);
char mc='0';
for(int i=1;i<=n;i++)
{
if(ss[i]>mc)
{
mc=ss[i];
cnt=0;
p[++cnt]=i;
}
else if(ss[i]==mc)
p[++cnt]=i;
}
if(cnt==1)
{
printf("%c\n",mc);
return 0;
}
int num=1,e=n-p[1];
for(int i=1;i<=n-p[1];i++)
{
char maxn='0';
int m=0;//f=0;
for(int j=1;j<=cnt;j++)
{
if(p[j]==0||ss[p[j]+i]=='\0')
continue;
if(ss[p[j]+i]>maxn)
maxn=ss[p[j]+i];
}
for(int j=1;j<=cnt;j++)
{
if(p[j]==0)
continue;
if(ss[p[j]+i]=='\0'||ss[p[j]+i]<maxn)
p[j]=0;
if(p[j]!=0)
m++;
}
if(m==1)
{
for(int j=1;j<=cnt;j++)
{
if(p[j]!=0)
{
num=j;
e=i;
break;
}
}
break;
}
}
printf("%s\n",ss+p[num]);
return 0;
}
B.阶乘：
分析：
先把 进行质因数分解，然后二分，求出满足条件的最小
。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int maxn=1e5;
bool vis[N];
vector<int>prime;
int e[N],num[N],cnt;
void init()//先筛出1e5以内的素数，加快质因子分解的速度
{
memset(vis,0,sizeof(vis));
for(int i=2;i<=maxn;i++)
{
if(!vis[i]){
prime.push_back(i);
}
for(int j=0;j<prime.size()&&prime[j]*i<=maxn;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
}
}
void divide(int n)//质因子分解，记录每个质因子及其幂的大小
{
cnt=0;
for(int i=0;i<prime.size()&&1LL*prime[i]*prime[i]<=n;i++)
{
if(n%prime[i]==0)
{
num[++cnt]=prime[i];
e[cnt]=0;
while(n%prime[i]==0)
{
n/=prime[i];
e[cnt]++;
}
}
}
if(n>1)
{
e[++cnt]=1;
num[cnt]=n;
}
}
bool solve(ll n)//判断当前数的阶乘是否含有满足条件的质因子的数量
{
for(int i=1;i<=cnt;i++)
{
ll tn=n;
int res=0;
while(tn)
{
res+=(tn/num[i]);
tn/=num[i];
}
if(res<e[i])
return 0;
}
return 1;
}
int main()
{
int t,n;
init();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
divide(n);
ll l=1,r=n;
while(l<=r)
{
ll mid=(l+r)>>1;
if(!solve(mid))
l=mid+1;
else
r=mid-1;
}
printf("%lld\n",l);
}
return 0;
}
G.树上求和：
分析：
贪心，用的次数越多的边其边权尽可能的小。可以先遍历整棵树，求出每个点所在子树的大小，便可以知道每条边两端的端点的数量，相乘即为该边所在路径的数量。按所在路径数从大到小排序，赋予从小到大的权值。
上有原题。
代码：
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e5+6;
struct edge
{
int from,to;
ll val;
bool operator < (const edge b)const
{
return val>b.val;
}
}e[N];
vector<int>pic[N];
int sz[N];
void dfs(int v,int p)
{
sz[v]=1;
for(int i=0;i<pic[v].size();i++)
{
int u=pic[v][i];
if(u!=p)
{
dfs(u,v);
sz[v]+=sz[u];
}
}
}
int main()
{
int n,u,v;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
pic[u].pb(v);
pic[v].pb(u);
e[i].from=u;
e[i].to=v;
}
dfs(1,0);
ll ans=0;
for(int i=1;i<n;i++)
{
int a=e[i].from;
int b=e[i].to;
int t=min(sz[a],sz[b]);
e[i].val=1LL*t*(n-t);
}
sort(e+1,e+n);
for(int i=1;i<n;i++)
{
int a=e[i].from;
int b=e[i].to;
int t=min(sz[a],sz[b]);
ans+=(1LL*i*t*(n-t));
}
printf("%lld\n",ans);
return 0;
}
A.膜法记录：
分析：
贪心，先把能消灭一整行的次数用完，使得剩下的列尽量少，然后看看看剩下的列有多少个，和 比较一下大小。
先把各种状态的列的数量统计，然后 枚举对行进行的操作种类，并记录下使用该种操作，可以消除哪些行，这时需要求子集前缀和最后遍历所有操作种类，找出符合条件的即可。
如果 表示
是
的子集。
if(!(j&(1<<(i-1))))//表示方案j不包括第i行
num[j|(1<<(i-1))]+=num[j];//求出包含j，比j都第i位的方案，求子集前缀和 ：用于计算
的二进制表示中
的个数。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char ss[25][N];
int num[N];
int main()
{
int t,n,m,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&n,&m,&a,&b);
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++)
scanf("%s",ss[i]+1);
for(int j=1;j<=m;j++)
{
int t=0;
for(int i=1;i<=n;i++)
t|=((ss[i][j]=='*'?1:0)<<(i-1));
num[t]++;//状态为 t 的列数
}
for(int i=1;i<=n;i++)//枚举每一行
{
for(int j=0;j<(1<<n);j++)//枚举方案
{
if(!(j&(1<<(i-1))))
num[j|(1<<(i-1))]+=num[j];//包含j的集合，子集前缀和
}
}
bool f=0;
for(int i=0;i<(1<<n);i++)
f|=(a>=__builtin_popcount(i)&&b>=m-num[i]);
printf("%s\n",f?"yes":"no");
}
return 0;
}
C.完全图：
分析：
按照贪心的思维，一个点一个点的把点分割出来。
分割出第 个点用边数：
分割出第 个点用边数：
...
按以上顺序分割点，分割 个点共需要
条边。
二分查找。
因为数据范围比较大，C++的话就要用高精度，所以偷个懒用 python。
方法通过指定分隔符对字符串进行分割并返回一个列表，默认分隔符为所有空字符，包括空格、换行(\n)、制表符(\t)等。也可以人为指定。
代码：
def solve(n,x):
return (2*n-x-1)*x/2
t=int(input())
for kase in range(t):
n, m = [int(x) for x in input().split()]#输入
l=int(1)
r=int(n)
while l<=r:
mid=int((l+r)/2)
if solve(n,mid-1)<m:
l=mid+1
else:
r=mid-1
if solve(n,l-1)>m or l>n:#二分查找到的是第一个大于等于m的数
l-=1
print(l) H.奇怪的背包问题增加了：
分析：
从高位向低位扫，把上一位缺的数保留到下一位，数量，直到能满足要求。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int k[N],num[35],vs[35];
int main()
{
int t,m;
scanf("%d",&t);
while(t--)
{
bool f=0;
scanf("%d",&m);
memset(num,0,sizeof(num));
memset(vs,0,sizeof(vs));
for(int i=1;i<=m;i++)
{
scanf("%d",&k[i]);
num[k[i]]++;
}
int cnt=1;
for(int i=30;i>=0;i--)
{
if(num[i]>=cnt)
{
vs[i]=cnt;
f=1;
break;
}
vs[i]=num[i];
cnt-=num[i];
cnt<<=1;
}
if(!f)
printf("impossible\n");
else
{
for(int i=1;i<=m;i++)
{
if(vs[k[i]]>0)
{
printf("1");
vs[k[i]]--;
}
else
printf("0");
}
printf("\n");
}
}
return 0;
}
京公网安备 11010502036488号