2019 牛客 多校赛 第五场
slove 1/10
rank 615
补题 6/10
--------------------------------------------------------
https://ac.nowcoder.com/acm/contest/885#question
A、digits 2
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n;
scanf("%d", &n);
int sum = n;
while (sum--)
printf("%d", n);
printf("\n");
}
} B、generator 1
给六个数字x1,x0,a,b,n,mod，对于n>=2，
方法1、循环节为 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll mod;
struct node
{
static const ll len = 2;
ll matrix[len][len];
node()
{
memset(matrix, 0, sizeof matrix);
}
void set(ll a[len][len])
{
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
matrix[i][j] = a[i][j];
}
}
void one()
{
for (int i = 0; i < len; i++)
matrix[i][i] = 1;
}
node operator * (node other)
{
node ans;
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
for (int k = 0; k < len; k++)
{
ans.matrix[i][j] += matrix[i][k] * other.matrix[k][j] % mod;
}
}
}
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
ans.matrix[i][j] %= mod;
}
}
return ans;
}
};
node power(node a, __int128 b)
{
node res;
res.one();
while (b)
{
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
char s[1000005];
__int128 len = 1;
void get(ll n)
{
for (int i = 2; i <= sqrt(n); i++)
{
if (n % i == 0)
{
len *= 1LL * (i - 1) * (i + 1);
while (n % i == 0)
n /= i;
}
}
if (n > 1)
{
len *= 1LL * (n - 1) * (n + 1);
}
}
int main()
{
ll a, b, q, w;
scanf("%lld%lld%lld%lld", &q, &w, &a, &b);
scanf("%s%lld", s, &mod);
len=mod;
get(mod);
int lens = strlen(s);
__int128 cnt = 0;
for (int i = 0; i < lens; i++)
{
cnt = (cnt * 10 + s[i] - '0') % len;
}
node res;
ll pre[2][2] = {
{w,0},
{q,0}
};
res.set(pre);
node t;
ll temp[2][2] = {
{a,b},
{1,0}
};
t.set(temp);
res = power(t, cnt - 1) * res;
printf("%lld\n", res.matrix[0][0]);
} 方法2、十进制暴力扫（可以优化为一、二、四、八次方来搞）
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll mod;
struct node
{
static const ll len = 2;
ll matrix[len][len];
node()
{
memset(matrix, 0, sizeof matrix);
}
void set(ll a[len][len])
{
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
matrix[i][j] = a[i][j];
}
}
void one()
{
for (int i = 0; i < len; i++)
matrix[i][i] = 1;
}
node operator * (node other)
{
node ans;
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
for (int k = 0; k < len; k++)
{
ans.matrix[i][j] += matrix[i][k] * other.matrix[k][j] % mod;
while (ans.matrix[i][j] >= mod)
ans.matrix[i][j] -= mod;
}
}
}
return ans;
}
};
node power(node a, ll b)
{
node res;
res.one();
while (b)
{
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
node t[4];
char s[1000005];
node res;
void update()
{
for (int i = 1; i <= 3; i++)
t[i] = t[i - 1] * t[i - 1];
}
int main()
{
ll a, b, q, w;
scanf("%lld%lld%lld%lld", &q, &w, &a, &b);
scanf("%s%lld", s, &mod);
ll pre[2][2] = {
{a,b},
{1,0}
};
ll tt[2][2] = {
{w,0},
{q,0}
};
node qq;
qq.set(tt);
t[0].set(pre);
update();
node res;
res.one();
int len = strlen(s);
for (int i = len - 1; i >= 0; i--)
{
int op = s[i] - '0';
for (int i = 0; i <= 3; i++)
if (op & (1 << i))
res = res * t[i];
t[0] = t[1] * t[3];
update();
}
res = res * qq;
printf("%lld\n", res.matrix[1][0]);
} F、maximum clique 1
题意:
给你n个点,每个点有一个数据,然后让你求一个最大团,满足每两个点的相异bit位数大于等于2.输出这个团的点的数目和里面的点
题解:
首先显然从正面看这是个最大团问题,但是明显,最大团求的一(ying)定(gai)会超时,也可能是我太菜了.所以考虑转换成补图求最大独立集问题.那么现在就是建图了.每两个bit相异位数恰为1的点相连一条边.可以使用网络流算法来求解.有一个细节问题就是如果把点分成两边.可以发现两个点可以连一条边必定一个点1的个数为奇数一个点1的个数为偶数,那么就可以分啦,奇数为一边,偶数为一边,然后跑网络流就好啦,
#include<bits/stdc++.h>
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep2(i,b,a) for(int i=b;i>=a;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pf push_front
#define pob pop_back
#define eb emplace_back
#define pof pop_front
#define sc scanf
#define pr printf
#define ll long long
using namespace std;
const int MAX = 5e3+5;
const int MAXN = 2e5+5;
const int INF = 0x3f3f3f3f;
int n,m,s,t,u[MAXN],v[MAXN],w[MAXN],q,a[MAX];
int first[MAX],nextt[MAXN];
int cur[MAX],cnt=0,answer=0,deep[MAX];
bool isLeft[MAX];
int read_int() {
char c;
int ret = 0, sgn = 1;
do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
if (c == '-') sgn = -1; else ret = c - '0';
while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
return sgn * ret;
}
void add(int a,int b,int c){
u[cnt]=a,v[cnt]=b,w[cnt]=c;
nextt[cnt]=first[u[cnt]];
first[u[cnt]]=cnt;++cnt;
}
bool bfs(){
deque<int>list1;
list1.eb(s);
for(int i=1;i<=n+2;++i) deep[i]=0;
memset(deep,0,sizeof(deep));
deep[s]=1;
while(!list1.empty()){
int now = list1.front();list1.pof();
if(now==t) return true;
for(int num = first[now];num!=-1;num=nextt[num]){
if(!deep[v[num]]&&w[num]>0){
deep[v[num]]=deep[now]+1;
list1.eb(v[num]);
}
}
}
return false;
}
int dfs(int now,int limit){
if(!limit||now==t) return limit;
int flow=0,length=0;
for(int &num = cur[now];num!=-1;num=nextt[num]){
if(w[num]&&deep[v[num]]==deep[now]+1 && (length = dfs(v[num],min(limit,w[num])))){
w[num]-=length;
w[num^1]+=length;
flow+=length;
limit-=length;
if(!limit) break;
}
}
if(flow) return flow;
deep[now]=-1;
return 0;
}
void dinic(){
while(bfs()){
for(int i=1;i<=n+2;++i) cur[i]=first[i];
int d = dfs(s,INF);
if(!d) break;
answer+=d;
}
}
int oneCount(int num){
int count=0;
while(num){
if(num&1) ++count;
num>>=1;
}
return count;
}
void solve(){
n = read_int();
// scanf("%d",&n);
s=n+1,t=n+2,cnt=0,answer=0;
for(int i=1;i<=n+2;++i) first[i]=-1;
for(int i=1;i<=n;++i){
a[i]=read_int();
// scanf("%d",&a[i]);
if(oneCount(a[i])&1) isLeft[i]=true;
if(isLeft[i]) add(s,i,1),add(i,s,0);
else add(i,t,1),add(t,i,0);
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(oneCount(a[i]^a[j])==1){
if(isLeft[i]) add(i,j,1),add(j,i,0);
else add(j,i,1),add(i,j,0);
}
}
}
dinic();
int ans = n-answer;
printf("%d\n",ans);
for(int i=1;i<=n;++i){
if(deep[i]!=0&&isLeft[i]) printf("%d ",a[i]);
else if(deep[i]==0&&!isLeft[i]) printf("%d ",a[i]);
}
printf("\n");
}
int main(void)
{
solve();
return 0;
} G、subsequence 1
题意：
给出两个字符串s1 s2 求出s1中子序列大于s2的子序列个数
jzk做法
从后往前枚举大于等于m的子串的数量，再算出所有大于长度大于m的子串
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
const ll mod = 998244353;
const int MAXN = 3005;
using namespace std;
ll C[MAXN][MAXN];
ll dp[MAXN][MAXN];
void init()
{
for (int i = 0; i < MAXN; i++)
C[i][0] = 1;
for (int i = 1; i < MAXN; i++)
for (int j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
char s1[MAXN], s2[MAXN];
int main()
{
init();
int T;
sc("%d", &T);
while (T--)
{
int n, m;
sc("%d%d", &n, &m);
sc("%s%s", s1, s2);
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
dp[i][j] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i && j <= m; j++)
{
dp[i][j] = dp[i - 1][j];
if (s1[n - i] == s2[m - j])//首字母相等，等于之前选的数量
dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
else if (s1[n - i] > s2[m - j])//首字母大于，随便选
dp[i][j] = (dp[i][j] + C[i - 1][j - 1]) % mod;
}
}
ll ans = dp[n][m];//长度等于m的大于s2串的个数
for (int i = 1; i <= n; i++)//长度大于m的个数
if (s1[i - 1] != '0')
for (int j = m; j <= n - i; j++)
ans = (ans + C[n - i][j]) % mod;
pr("%lld\n", ans);
}
} --------------------------------------------------------
dh做法
做法：
首先考虑如果子序列长度大于s2的长度则必定大于。这一部分可以用组合数的方式直接算出来。然后便是考虑长度相等的情况，这一部分考虑DP 第二维表示的是子序列长度，第三维表示的是在长度相等的情况下，0代表s1子序列在长度相等的情况下值相等s2，1代表s1子序列在长度相等的情况下值大于s2
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 998244353;
const int N = 3005;
ll dp[N][N][2];
ll C[N][N];
char s1[N], s2[N];
int main()
{
for (int i = 1; i < N; i++)
{
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++)
{
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
if (C[i][j] >= MOD)
C[i][j] -= MOD;
}
}
int T;
scanf("%d", &T);
while (T--)
{
int m, n;
scanf("%d %d", &m, &n);
scanf("%s %s", s1+1, s2+1);
for(int i = 0;i<=m;i++)
for(int j = 0;j<=n;j++)
for(int k = 0;k<=1;k++)
dp[i][j][k] = 0;
dp[0][0][0] = 1;
for (int i = 1; i <= m; i++)
{
for (int j = 0; j <= n; j++)
for (int k = 0; k <= 1; k++)
dp[i][j][k] = dp[i - 1][j][k];
for (int j = 1; j <= n; j++)
{
for (int k = 0; k <= 1; k++)
{
if (k == 0 && s1[i] < s2[j])
continue;
if (k == 0 && s1[i] == s2[j])
(dp[i][j][k] += dp[i - 1][j - 1][k]) %= MOD;
else
(dp[i][j][1] += dp[i - 1][j - 1][k]) %= MOD;
}
}
}
ll ans = dp[m][n][1];
for(int i = 1;i<=m;i++)
if (s1[i] != '0')
{
for (int j = n; i + j <= m; j++)
(ans += C[m - i][j]) %= MOD;
}
printf("%lld\n", ans);
}
}
/*
3
4 2
1234
13
*/
H、subsequence 2
题意:大概就是原来有一个隐藏字符串,然后给你n个字符串,然后把那个给出字符串中没出现的字母在隐藏字符串中删掉,然后就得到了这个字符串,然后让你根据这n个字符串求原来的隐藏字符串
题解:
直接根据给出的字符串建立拓扑序,给每个出现的字母编号,比如说给出的字符串为:
bbc
ac
abb
那么编号就是
123
43
412
然后求出拓扑序列,这里的拓扑序为4123,那么明显字符串为abbc(没考虑长度限制!!不要和题目里的样例搞混了,因为样例里是不可以的,因为样例里长度只能为3).
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e6+5;
const int MAXN = 1e2+5;
int n,m,len,tot=0;
char s1[MAXN],s2[MAX];
bool vis[30],visit[MAX];
int mp[MAX];
int indexMy[30][MAX],cnt[30],now[30],pre,du[MAX];
int first[MAX],nextt[MAX],u[MAX],v[MAX],total=0;
vector<int> ans;
void add(int a,int b){
u[total]=a,v[total]=b;
nextt[total]=first[u[total]];
first[u[total]]=total;++total;
}
void topology(){
deque<int> list1;
for(int i=0;i<tot;++i){
if(du[i]==0){
list1.push_back(i);
}
}
while(!list1.empty()){
int now = list1.front();
list1.pop_front();
ans.push_back(now);
for(int num = first[now];num!=-1;num=nextt[num]){
--du[v[num]];
if(du[v[num]]==0){
list1.push_back(v[num]);
}
}
}
}
void solve(){
memset(cnt,0,sizeof(cnt));
memset(vis,false,sizeof(vis));
memset(first,-1,sizeof(first));
memset(visit,false,sizeof(visit));
memset(du,0,sizeof(du));
scanf("%d%d",&n,&m);
for(int i=0;i<m*(m-1)/2;++i){
memset(now,0,sizeof(now));
scanf("%s%d",s1+1,&len);
if(len!=0) scanf("%s",s2+1);
for(int j=1;s2[j];++j){
if(!vis[s2[j]-'a']){
mp[tot]=s2[j]-'a';
indexMy[s2[j]-'a'][cnt[s2[j]-'a']++]=tot++;
}
if(j!=1){
int a = pre,b = indexMy[s2[j]-'a'][now[s2[j]-'a']];
add(a,b);
++du[b];
}
pre = indexMy[s2[j]-'a'][now[s2[j]-'a']];
++now[s2[j]-'a'];
}
for(int j=1;s1[j];++j) vis[s1[j]-'a']=true;
}
// printf("tot = %d\n",tot);
// printf("mp:\n");
// for(int i=0;i<tot;++i){
// printf("%c ",(char)(mp[i]+'a'));
// }
// printf("\n");
// for(int i=0;i<26;++i){
// printf("%c: ",(char)(i+'a'));
// for(int j=0;j<cnt[i];++j){
// printf("%d ",indexMy[i][j]);
// }
// printf("\n");
// }
topology();
if(ans.size()!=n){
printf("-1\n");
return;
}
for(int i=0;i<ans.size();++i){
printf("%c",(char)(mp[ans[i]]+'a'));
}
}
int main(void)
{
solve();
return 0;
} I、three points 1
题意，给一个三角形的三边和矩形的长宽，问三角形能否完全放入矩形
1、首先三角形至少有一个顶点与矩形的顶点重合，并且除了这个点至少有一个点在矩形的边上，所以就可以暴力，三角函数乱搞。
2、注意要按照顺序输出三个点，WA到自闭
#include <bits/stdc++.h>
const double eps = 1e-8;
const double PI = acos(-1.0); // PI = 180°= 3.14
using namespace std;
int sign(double x)
{
if (fabs(x) < eps)
return 0;
return x > 0 ? 1 : -1;
}
struct point
{
double x;
double y;
void print() { printf("%.12lf %.12lf ", x, y); }
void println() { printf("%.12lf %.12lf\n", x, y); }
};
double getlen(point a, point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
bool check(point a, double w, double h)
{
if (sign(a.x - w) <= 0 && sign(a.x) >= 0 && sign(a.y - h) <= 0 && sign(a.y) >= 0)
return true;
return false;
}
bool judge(double w, double h, double a, double b, double c, int op)
{
point one = point{ 0,0 };
point two, ans;
double anglec = acos((a * a + b * b - c * c) / (2 * a * b));
if (a <= h)
two = point{ 0,a };
else
two = point{ sqrt(a * a - h * h) ,h };
double angle = acos((a * a + c * c - b * b) / (2 * a * c)) + atan(two.x / two.y);
ans.x = c * sin(angle);
ans.y = c * cos(angle);
if (check(ans, w, h) && check(two, w, h))
{
switch (op)
{
case 0: two.print(), one.print(), ans.println(); break;
case 1: one.print(), two.print(), ans.println(); break;
case 2: two.print(), ans.print(), one.println(); break;
case 3: one.print(), ans.print(), two.println(); break;
case 4: ans.print(), two.print(), one.println(); break;
case 5: ans.print(), one.print(), two.println(); break;
}
return false;
}
return true;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
double w, h, a, b, c;
scanf("%lf%lf%lf%lf%lf", &w, &h, &a, &b, &c);
if (judge(w, h, a, b, c, 0))
if (judge(w, h, a, c, b, 1))
if (judge(w, h, b, a, c, 2))
if (judge(w, h, b, c, a, 3))
if (judge(w, h, c, a, b, 4))
judge(w, h, c, b, a, 5);
}
}
投递拼多多集团-PDD等公司10个岗位 >
查看5道真题和解析