|
第一次写博客，用来记录补题情况。
B2. Wonderful Coloring - 2
这道题卡了我1个多小时才做出来，再写了一遍之后发现要处理的东西确实挺多的，思维还是太弱了。具体做法是先记录可以给颜色的数，然后给这些数颜色，要是剩余没给颜色的数达不到一轮（即k种颜色），直剩余的全部赋值为0
C. Interesting Story
没做出来，对sort有误解，一直认为使用sort会超时。
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#define met(a) memset(a,0,sizeof(a));
using namespace std;
typedef long long ll;
const int M=200005;
string s[M];
vector<int>a;
int main(){
int t;
cin>>t;
while(t--){
int n;
int ans1=0;
cin>>n;
for(int i=0;i<n;i++)cin>>s[i];
for(int i=0;i<5;i++){
a.clear();
for(int j=0;j<n;j++){
int ans=0;
for(int k=0;k<s[j].size();k++){
if(s[j][k]-'a'==i){
ans++;
}else ans--;
}
a.push_back(ans);
}
sort(a.begin(),a.end());
int ans=0;
int sum=0;
for(int j=n-1;j>=0;j--){
if(ans+a[j]<=0){
break;
}
++sum;
ans+=a[j];
}
ans1=max(ans1,sum);
}
cout<<ans1<<endl;
}
}
D1. Domino (easy version)
题意：用K个12的矩形和（nm/2-K）个21的矩形构成一个nm的矩形
分析：感觉比B2简单，首先看n行和m列是否为偶数，如果不是偶数，先把多的那一行用特定矩形填充，填充不了则为NO，然后处理n和m都为偶数的矩形，两种特殊矩阵都必须为偶数才能构成这个矩形
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#define met(a) memset(a,0,sizeof(a));
using namespace std;
typedef long long ll;
const int M=200005;
int main(){
int t;
cin>>t;
while(t--){
int n,m,k;
cin>>n>>m>>k;
int z=n*m/2-k;
if(n%2==1){
int l=m/2;
if(k<l)cout<<"NO\n";
else{
if((k-l)%2==1){
cout<<"NO\n";
}else{
cout<<"YES\n";
}
}
}
else if(m%2==1){
int l=n/2;
if(z<l)cout<<"NO\n";
else{
if((z-l)%2==1)cout<<"NO\n";
else cout<<"YES\n";
}
}
else{
if(k%2==1)cout<<"NO\n";
else cout<<"YES\n";
}
}
}
D2. Domino (hard version)
题意：大致如D1，然后输出一个满足的方案。同时每个12或21的矩形的两个单元必须为同一字母，且有同一边的另一个矩形不能与这个矩形的字母相同。
分析：给填充奇数的边以yz两个字母交替，因为每2个12或21的矩形必须连在一起构成22的矩形，所以以22的矩形去填充，12构成的22在奇数列和偶数列不能一样，21构成的22在奇数行和偶数行不能一样。
代码写得有点乱，不贴了。
E. Fixed Points
题意：给定一个序列，问减去n个数，使序列a[i]==i的数>=k,同时使得这个n最小，问这个n
分析：对序列每个数进行i-a[i]操作，即求得每个位置的数需要减去多少个数，使得a[i]=i。然后进行dp操作，dp[n][i]表示n长度删去i个数所能得到的最多a[i]=i。
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#define met(a) memset(a,0,sizeof(a));
using namespace std;
typedef long long ll;
const int M=2222;
int a[M];
int s[M];
int dp[M];
int main(){
int t;
cin>>t;
while(t--){
int ans=M;
memset(dp,0,sizeof(dp));
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=i-a[i];
}
for(int i=1;i<=n;i++){
int z=s[i];
for(int j=i;j>0;j--){
if(j!=z)dp[j]=max(dp[j],dp[j-1]);
else dp[j]=max(dp[j]+1,dp[j-1]);
}
if(z==0)dp[0]+=1;
if(dp[z]>=k&&z>=0){
ans=min(ans,z);
}
}
if(ans!=M)cout<<ans<<endl;
else cout<<"-1\n";
}
}
F. Equidistant Vertices
分析：想了几个方法，最终实现起来才发现总是忽略了很多条件，然后写出了一个TLE的代码，实在没办法看了下其他人的代码，把找组合数的递归改为动态规划就过了，写得有点乱了。
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<queue>
#define met(a) memset(a,0,sizeof(a));
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int M=210;
int k;
int cnt;
ll ans;
int n;
int F;
int max1;
int next1[M];
ll dp[M][M];
int head[M];
int qu[M];
int len[M];
int d[M][M];
int vec[M];
void add(int u,int v){
next1[++cnt]=head[u];
qu[cnt]=v;
head[u]=cnt;
}
void solve(int u,int c,int fa){
d[u][c]=1;
for(int i=head[u];i;i=next1[i]){
int v=qu[i];
if(v==fa)continue;
solve(v,c+1,u);
for(int j=c+1;j<=max(c,max1);j++){
d[u][j]+=d[v][j];
if(u!=F)d[v][j]=0;
}
}
max1=max(c,max1);
}
void dfs(int *ve,int n1,int c,int ge,ll sum){
if(c>=n1)return;
dfs(ve,n1,c+1,ge,sum);
sum=((ll)ve[c]*sum)%mod;
if(ge==k-1)ans=(ans+sum)%mod;
else dfs(ve,n1,c+1,ge+1,sum);
}
void get(int u){
int flag=0;
for(int j=1;j<=max1;j++){
int sum=0;
for(int i=head[u];i;i=next1[i]){
int v=qu[i];
if(d[v][j]!=0){
vec[sum]=d[v][j];
d[v][j]=0;
sum++;
}
}
if(sum>=k&&!flag){
for(int i=0;i<=n;i++){
for(int i1=0;i1<=k;i1++)dp[i][i1]=0;
}
dp[0][0]=1;
for(int i=1;i<=sum;i++){
for(int l=0;l<=k;l++)
dp[i][l]=dp[i-1][l];
for(int l=1;l<=k;l++){
ll z1=(ll)(dp[i][l]+(dp[i-1][l-1]*vec[i-1]));
z1%=mod;
dp[i][l]=z1;
}
}
ans+=dp[sum][k];
ans%=mod;
}
else flag=1;
}
}
int main(){
int t;
cin>>t;
while(t--){
memset(len,0,sizeof(len));
ans=0;
cnt=0;
cin.get();
cin>>n>>k;
memset(head,0,sizeof(head));
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
len[u]++;
len[v]++;
add(u,v);
add(v,u);
}
if(k==2){
cout<<n*(n-1)/2<<endl;
continue;
}
for(int i=1;i<=n;i++){
if(len[i]<k)continue;
max1=0;
F=i;
solve(i,0,0);
get(i);
for(int j=0;j<=max1;j++){
d[i][j]=0;
}
}
cout<<ans<<endl;
}
}
总结：思维性的偏多，都是以基础算法出的，模拟能力太差了，导致了写代码出错率高并且写得又慢。
|