A Paint the Numbers
直接循环下
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 110;
int a[MAXN],ans;
int main()
{
int n,i;
scanf("%d",&n);
for(i = 1;i <= n;i++)
scanf("%d",&a[i]);
sort(a + 1,a + 1 + n);
for(i = 1;i <= n;i++)
{
bool able = 1;
for(int j = 1;j < i;j++)
if(a[i] % a[j] == 0)
{
able = 0;
break;
}
if(able) ans++;
}
printf("%d",ans);
return 0;
}
B Koala and Lights
题目大意
有n盏灯（(1≤n≤100)） 每盏灯有两种状态（开或关），给定每盏灯的初始状态（一个01字符串 0-关，1-开）
接下来每盏灯对应给出它的(a)和(b(1≤a,b ≤5 ))
这些灯在(b+a*k (kin [0,+infty)))时刻会改变状态
问 同一个时刻最多有多少灯同时亮着
因为((1≤a,b ≤5 ))
考虑一下这个范围 求一下lcm
大概暴力循环到200就够了
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 110;
bool sta[MAXN];
struct node
{
int a,b;
}w[MAXN];
int ans;
int main()
{
int j,i,n;
scanf("%d",&n);
for(i = 1;i <= n;i++) scanf("%1d",&sta[i]);
for(i = 1;i <= n;i++)
scanf("%d%d",&w[i].a,&w[i].b);
for(i = 0;i <= 200;i++)
{
int q = 0;
for(j = 1;j <= n;j++)
{
if(i >= w[j].b&&(i - w[j].b) % w[j].a == 0) sta[j] = !sta[j];
if(sta[j]) q++;
}
ans = max(ans,q);
}
printf("%d",ans);
return 0;
}
C Paint the Digits
比较简单
用单调队列 处理完1的
但此时涂1不一定有这么多，判断一下涂2的最小的
把涂1的大于涂2的最小的数给添加到涂2里就搞定了
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 2e5 + 1;
int d[MAXN],cnt;
struct node
{
int val,loc;
}q[MAXN];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,i,j;
scanf("%d",&n);
cnt = 0;
q[cnt].val = -1;
for(i = 1;i <= n;i++)
scanf("%1d",&d[i]);
for(i = 1;i <= n;i++)
{
while(q[cnt].val > d[i]) cnt--;
q[++cnt].val = d[i];
q[cnt].loc = i;
}
j = 1;
//处理涂1的
int fi = 0;
for(i = 1;i <= n;i++)
{
if(d[i] == q[j].val&&j <= cnt) j++;
else {
fi = i;
break;
}
}
//找最小（不是指大小，而是位置）的涂2的
if(fi)
{
while(q[cnt].val > d[fi]) cnt--;
j = 1;
bool able = 0;
int maxl = 0;
for(i = 1;i <= n;i++)
if(d[i] == q[j].val&&j <= cnt) j++;
else {
maxl = max(maxl,d[i]);
if(d[i] < maxl)
{
able = 1;
break;
}
}
if(able)
{
printf("-
");
continue;
}
}
j = 1;
for(i = 1;i <= n;i++)
if(d[i] == q[j].val&&j <= cnt) {printf("1");j++;}
else printf("2");
putchar('
');
}
return 0;
}
D Cow and Snacks
相当于是一个森林
易得每一棵树最大解为边数(-1)
然后再累加起来用(n)减它就是(ans)
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 1;
vector<int> G[MAXN];
int ans;
bool vis[MAXN],d[MAXN];
inline void dfs(int x)
{
ans++;//
vis[x] = 1;
int i;
for(i = 0;i < G[x].size();i++)
{
int v = G[x][i];
if(!vis[v])
dfs(v);
}
}
int main()
{
int i,n,k;
scanf("%d%d",&n,&k);
for(i = 1;i <= k;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
d[u] = d[v] = 1;
}
for(i = 1;i <= n;i++)
if(!vis[i]&&d[i])
{
dfs(i);
ans--;
}
printf("%d",k - ans);
return 0;
}
E Rotate Columns (easy version)
这道题对我来说不是很简单
因为这道题要用状压(DP)
而我没学
(color{pink}{然而学会之后还是挺简单的})
其实就是把一维记录状态
而这状态为(10)进制数
把她转为二进制
得到一个(01)字符串
分别对应每一列的状态
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int num[15][2010],dp[2010][4100],n;
inline int count(int x,int s)
{
int i,j,ans = 0;
for(i = 1;i <= n;i++)
{
int sum = 0,k = 1;
for(j = 1;j <= n;j++)
{
if(k & s)
sum += num[j][x];
k <<= 1;
}
当前的取值
ans = max(ans,sum);
for(j = n;j >= 1;j--)
num[j + 1][x] = num[j][x];
num[1][x] = num[n + 1][x];
把数字往后移一位
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int i,j,m;
scanf("%d%d",&n,&m);
for(i = 1;i <= n;i++)
for(j = 1;j <= m;j++)
scanf("%d",&num[i][j]);
int maxl = (1 << n) - 1,k;
到这里 应该很容易看出来了
dp[i][j]表示在前i列中 选取状态为j的最优解
for(i = 1;i <= m;i++)
{
memset(dp[i],0,sizeof(dp[i]));
for(j = 0;j <= maxl;j++)
{
for(k = j;;k = (k - 1) & j)
{
dp[i][j] = max(dp[i][j],dp[i - 1][k] + count(i,j - k));
if(!k) break;
}
}
}
DP
printf("%d
",dp[m][maxl]);
}
return 0;
}
F Rotate Columns (hard version)
会(E)题的话这题就很好做了
(color{pink}{大水题})
把每列的最大值记录下 按其大小从大到小排序
然后只算前(n)个
还有就是 把(count(i,j - k))预处理一下
但我的代码真的很神奇
讲道理循环到(n)就可以AC了
我改成(n+5)才过
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int num[15][2010],dp[2010][4100],n;
int cnt[2010][4100];
struct node
{
int maxl,it;
bool operator <(const node y) const {return maxl > y.maxl;}
}row[2010];
inline int count(int x,int s)
{
int i,j,ans = 0;
for(i = 1;i <= n;i++)
{
int sum = 0,k = 1;
for(j = 1;j <= n;j++)
{
if(k & s) sum += num[j][row[x].it];
k <<= 1;
}
ans = max(ans,sum);
for(j = n;j >= 1;j--)
num[j + 1][row[x].it] = num[j][row[x].it];
num[1][row[x].it] = num[n + 1][row[x].it];
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int i,j,m;
scanf("%d%d",&n,&m);
for(i = 1;i <= n;i++)
for(j = 1;j <= m;j++)
{
scanf("%d",&num[i][j]);
if(i == 1) row[j].it = j,row[j].maxl = num[i][j];
row[j].maxl = max(row[j].maxl,num[i][j]);
}
memset(cnt,0,sizeof(cnt));
sort(row + 1,row + 1 + m);
int maxl = (1 << n) - 1,k,ans = 0;
for(i = 1;i <= min(n + 5,m);i++)
for(j = 0;j <= maxl;j++)
cnt[i][j] = count(i,j);
for(i = 1;i <= min(n + 5,m);i++)
{
memset(dp[i],0,sizeof(dp[i]));
for(j = 0;j <= maxl;j++)
{
for(k = j;;k = (k - 1) & j)
{
dp[i][j] = max(dp[i][j],dp[i - 1][k] + cnt[i][j - k]);
ans = max(ans,dp[i][j]);
if(!k) break;
}
}
}
printf("%d
",ans);
}
return 0;
}
G Koala and Notebook
这题得用拆点
之前没学过 然后这次学会了
所以打比赛使人进步
拆点的思路很简单
拆点的本质是拆边
我们这道题 把每条边 拆成 其位数条边 每条边的权值为其对应该位的数
输入
for(i = 1;i <= m;i++)
{
int j,u,v,k = i;
scanf("%d%d",&u,&v);
edge.clear();
while(k) {edge.push_back(k % 10);k /= 10;}
int Size = edge.size(),pre = u;
for(j = Size - 1;j >= 0;j--)
{
int w = (j == 0? v:++cnt);
V[pre][edge[j]].push_back(w);
pre = w;
}
pre = v;
for(j = Size - 1;j >= 0;j--)
{
int w = (j == 0? u:++cnt);
V[pre][edge[j]].push_back(w);
pre = w;
}
}
然后 我是用循环模拟的(BFS)
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 1;
const int MOD = 1e9 + 7;
vector<int> edge,V[MAXN][10],Q[MAXN];
int ans[MAXN];
bool vis[MAXN];
int main()
{
int i,n,m,cnt,j;
scanf("%d%d",&n,&m);
cnt = n;
for(i = 1;i <= m;i++)
{
int j,u,v,k = i;
scanf("%d%d",&u,&v);
edge.clear();
while(k) {edge.push_back(k % 10);k /= 10;}
int Size = edge.size(),pre = u;
for(j = Size - 1;j >= 0;j--)
{
int w = (j == 0? v:++cnt);
V[pre][edge[j]].push_back(w);
pre = w;
}
pre = v;
for(j = Size - 1;j >= 0;j--)
{
int w = (j == 0? u:++cnt);
V[pre][edge[j]].push_back(w);
pre = w;
}
}
int dep = 0;
Q[++dep].push_back(1);
vis[1] = 1;
for(i = 1;i <= dep;i++)
for(int w = 0;w < 10;w++)
{
bool able = 0;
for(j = 0;j < Q[i].size();j++)
{
int u = Q[i][j];
for(int k = 0;k < V[u][w].size();k++)
{
int v = V[u][w][k];
if(vis[v]) continue;
vis[v] = able = 1;
Q[dep + 1].push_back(v);
ans[v] = (ans[u] * 10ll + w) % MOD;
}
}
if(able) dep++;
}
BFS
for(i = 2;i <= n;i++) printf("%d
",ans[i]);
return 0;
}
Sum up
后面三道题我也不会了
这次的题不难
但我的分数很低 只做对了AB题
值得反思
我也还需要多打比赛 多练题
把手感找到