投稿
  1. 首页
  2. 随笔

SDNU

苏州博客门 • 2022-12-17 • 随笔 • 阅读 21

SDNU,第1张

SDNU

寒假的第一场训练补题。全英文的题欸，，，看懂题意都费劲QAQ

本次比赛罚时离谱，主要是犯同一个错误次数太多：没开long long，，，麻了

A - Knapsack for All Segments

 主要意思是说给出序列A，给出一个正整数S，在每一个区间中一共有多少子区间的和为S。

思路：参考

 AC代码：

#include

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=998244353;
const int N=3e3+5;
int n,s;
int a[N];
ll ans,f[N];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
    	f[0]+=1;
    	for(int j=s;j>=a[i];j--)
    	f[j]=(f[j]+f[j-a[i]])%mod;
    	ans=(ans+f[s])%mod;
	}
	cout<

os：DP好难想QWQ

B - Dividing Chocolate

 主要意思是说有一块给出长宽的巧克力，白色为1，黑色为0，每次选择一行一列横切竖切，（切是从开始一直切到头），求切多少刀可以满足每块巧克力上的白色部分小于等于所给值。

思路：H的范围很小，直接暴力枚举横切的情况，再贪心竖切。对于枚举横切时，我们可以用0代表不切，1代表切，用__builtin_popcount()计算有多少个位为1。参考代码解释很详细

AC代码：

#include

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int h,w,k;
string s[12];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>h>>w>>k;
    for(int i=0;i>s[i];
    int ans=INF;
    for(int l=0;l<(1<<(h-1));l++)
    {
    	int x=__builtin_popcount(l);
    	int r[x+1]={0};
    	int flag=1,cnt=x;
    	for(int j=0;jk)
			{
				flag=0;
				break;
			}
			maxn=0;
			for(int i=0;i<=x;i++)
			maxn=max(maxn,r[i]+c[i]);
			if(maxn>k)
			{
				memset(r,0,sizeof(r));
				cnt++;
			}
			for(int i=0;i<=x;i++) r[i]+=c[i];
		}
		if(flag) ans=min(ans,cnt);
	}
	cout<

os：二进制处理问题，这种想法没怎么用过欸

C - Maximum Volume

主要意思是说给出一个正整数L，是长方体长宽高的和，问组成的长方体最大体积是多少。

思路：当n个数和一定时，每个数相等时，n个数的积最大。

AC代码：

#include

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int l;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>l;
	double a=(double)l/3.0;
    printf("%.7lfn",a*a*a);
	return 0;
}

os：这个题还WA了一发，因为多输出东西了。

D - String Palindrome

 主要意思是说判断一个字符串是否是强回文串，满足以下三个条件的是强回文串。

思路：主要用的substr()函数，还有resreve()函数。

AC代码：

#include

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;

bool pan(string s)
{
	string a=s;
	reverse(s.begin(),s.end());
	string b=s;
	if(a==b) return true;
	else return false;
} 

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    string s;
    cin>>s;
    int len=s.length();
    string m=s.substr(0,(len-1)/2);
    string n=s.substr((len+3)/2-1,len-(len+3)/2+1);
    if(pan(s)&&pan(m)&&pan(n)) cout<<"Yes"<<'n';
    else cout<<"No"<<'n';
	return 0;
}

os：前几天打cf学到的函数就用上了：P

 E - Banned K

主要意思是说从k=1开始一直到k=n，对于数列每次去掉a[k]一个元素，剩下的元素可以选出多少对大小相等的数。

思路：遍历数组，将每个元素有多少统计一下，对于1,1,1，一共有3种选法，即2+1，推广来说，就是对于一个有n个的元素，种类数为1+2+......+(n-1)。

AC代码：

#include

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=2e5+5;
ll n;
ll a[N],cnt[N],c[N],flag[N];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n;
    for(ll i=1;i<=N-2;i++)
    {
    	if(i==1) c[i]=1;
    	else c[i]=c[i-1]+i;
	}
	ll ans=0;
    for(ll i=1;i<=n;i++)
    {
    	cin>>a[i];
    	cnt[a[i]]++;
	}
	for(ll i=1;i<=n;i++)
	{
		if(!flag[a[i]])
		{
			ans+=c[cnt[a[i]]-1];
			flag[a[i]]=1;
		}
		
	}
	for(ll i=1;i<=n;i++)
	{
		cout<

os：多做题多练的一大原因我觉得是在很多细节处理上会轻松一些。没开long longWA了一发。

F-Multiple of 2019

主要意思是说有一个S长度的字符串，仅由1~9组成，问字符串中有多少区间表示的十进制数是2019的倍数。

思路：用到同余方程。若x，y关于2019同余，那么可以写成x=a*2019+d，y=b*2019+d，则（x-y）%2019=0，那么就从后向前判断有多少区间满足[l,r]与[L,r](L

AC代码：

#include

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
string s;
ll ans,cnt,tmp;
vectorvec(2019);//用vector存余数

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>s;
    vec[0]=1;//余数为0的即符合条件
    int len=s.length();
    cnt=1;
    reverse(s.begin(),s.end());
    for(int i=0;i 
G-A Simple Problem with Integers  

 

主要意思是，，，别了，树状数组板子题。
 

思路：一维树状数组的区间修改，区间查询。
 

AC代码：
 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e5+10;
ll n,p;
ll sum1[N],sum2[N],a[N];

ll lowbit(ll x)
{
	return x&-x;
}

void update(ll pos,ll x)
{
	ll tmp=pos;
	while(pos<=n)
	{
		sum1[pos]+=x;
		sum2[pos]+=x*(tmp-1);
		pos+=lowbit(pos);
	}
}

ll query(ll x)
{
	ll tot1=0,tot2=0,tmp=x;
	while(x)
	{
		tot1+=sum1[x];
		tot2+=sum2[x];
		x-=lowbit(x);
	}
	return tot1*tmp-tot2;
}

int main()
{
//	freopen("test.in","r",stdin);
    scanf("%lld%lld",&n,&p);
    for(ll i=1;i<=n;i++)
    {
    	scanf("%lld",&a[i]);
    	update(i,a[i]-a[i-1]);
	}
	while(p--)
	{
		char p;
		cin>>p;
		if(p=='Q')
		{
			ll l,r;
			scanf("%lld%lld",&l,&r);
			printf("%lldn",query(r)-query(l-1));
		}
		else if(p=='C')
		{
			ll l,r,w;
			scanf("%lld%lld%lld",&l,&r,&w);
			update(l,w);
			update(r+1,-w);
		}
	}
	return 0;
}
 

os：板子题WA了好多次，因为没开long long。
 
H - Networking 

 

思路： 最小生成树板子题，kruskal做法。
 

AC代码：
 

#include

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=2555;
int n,m,ans;
int fa[N];

struct Edge
{
	int x,y,len;
	bool operator<(const Edge &a)
	{
		return len>n,n)
    {
    	cin>>m;
    	init();
        for(int i=1;i<=m;i++)
        cin>>e[i].x>>e[i].y>>e[i].len;
        sort(e+1,e+1+m);
        ans=0;
        for(int i=1;i<=m;i++)
        {
    	    if(getfa(e[i].x)!=getfa(e[i].y)) 
			{
				ans+=e[i].len;
				merge(e[i].x,e[i].y);
			}
	    }
	    cout<
 
J - base K 

 

主要意思是给出K进制的两个数，求这两个数在十进制下的乘积。
 

思路： 进制转换，开long long。
 

AC代码：
 

#include

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
ll k,a,b;

ll pmod(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b%2) res=res*a;
		b/=2;
		a=a*a;
	}
	return res;
}

ll func(ll n,ll l)
{
	ll d=0,i=0,r;
	ll ans=0;
	while(n)
	{
		r=n%10;
		ans+=r*pmod(l,i++);
		n/=10;
	}
	return ans;
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>k;
    cin>>a>>b; 
	ll cnt=func(a,k)*func(b,k);
    cout< 
K - Long Sequence 

 

主要意思是说给出序列A，序列B是序列A的很多次复制，给出一个值X，问序列B中前多少项和大于X。
 

思路： 如果直接把序列B遍历相加的话会TLE，那就先求序列A的和，把X模这个和的结果对A数组遍历求即可。
 

AC代码：
 

#include

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e5+5;
int n;
ll x,a[N];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    scanf("%d",&n);
    ll tt=0;
    for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		tt+=a[i];
	} 
	scanf("%lld",&x);
	ll ans=0,j;
	for(int i=1;i<=n;i++)
	{
		ans+=a[i];
		if(ans>x%tt)
		{
			j=i;
			break;
		}
	}
	cout< 

os：做题方法取决于数据大小！
 
L - 迷宫问题  

 

做过的原题了，属于记录路径的BFS，代码指路 传送门
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5711969.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
苏州博客门 苏州博客门 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存