A. Calculating Function
水题，分奇数偶数处理一下就好了
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
long long n;scanf("%lld",&n);
if(n%==) printf("%lld\n",(n-1LL)/2LL - n);
else printf("%lld\n",n/2LL);
}
B. OR in Matrix
比较机智的可以发现，对于每一个0，那么这一行和这一列都是-
对于每一个1，那么行或列，有一个1就好了
但是！有一个数据
1 0 0
1 0 0
1 0 0
这个数据应该是NO
#include<stdio.h>
#include<iostream>
using namespace std;
int a[][];
int vis1[];
int vis2[];
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(a[i][j]==)
{
vis1[i]=;
vis2[j]=;
}
}
}
int sum1=;
for(int i=;i<=n;i++)
sum1+=vis1[i];
int sum2=;
for(int i=;i<=m;i++)
sum2+=vis2[i];
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(a[i][j]==)
{
if(sum1==n||sum2==m)
{
printf("NO\n");
return ;
}
if(vis1[i]&&vis2[j])
{
printf("NO\n");
return ;
}
}
}
}
printf("YES\n");
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(vis1[i]||vis2[j])
{
printf("0 ");
}
else
printf("1 ");
}
printf("\n");
}
}
C. Palindrome Transformation
读题的时候，感觉这道题好熟悉，好像以前做过
在blog一搜，果然以前做过……
贪心就好了
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
const int maxn=+;
int main()
{
sspeed;
int n,pos;
string s;
cin>>n>>pos;
pos--;
if(pos>n/-)
pos=n-pos-;
cin>>s;
int ans=;
int l=,r=n/-;
while(l<n/&&s[l]==s[n-l-])
l++;
while(r>=&&s[r]==s[n-r-])
r--;
//cout<<l<<" "<<r<<endl;
if(l<=r){
for(int i=l;i<=r;i++)
{
int temp=abs(s[i]-s[n-i-]);
ans+=min(temp,-temp);
//cout<<ans<<endl;
}
ans=ans+min(abs(pos-r),abs(pos-l))+abs(l-r);
cout<<ans<<endl;
}
else
cout<<ans<<endl;
return ;
}
D. Valid Sets
暴力枚举每一个点为根，假设这个是这棵树的最大值，然后用乘法原则搞一搞就好了
对于每一棵子树，都有选与不选两种操作
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
#define maxn 2005
const int mod = 1e9 + ;
int a[maxn];
int d,n;
vector<int> G[maxn];
long long dfs(int x,int pre,int k)
{
long long ans = ;
for(int i=;i<G[x].size();i++)
{
int v = G[x][i];
if(v == pre || (a[k] == a[v]&&v > k))continue;
if(a[k]>=a[v]&&a[k]-a[v]<=d)
{
ans *= ( dfs(v,x,k) + );
while(ans>=mod)ans%=mod;
}
}
return ans;
}
int main()
{
scanf("%d%d",&d,&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<n;i++)
{
int u,v;scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
long long ans = ;
for(int i=;i<=n;i++)
{
ans += dfs(i,-,i);
while(ans>=mod)ans%=mod;
}
printf("%lld\n",ans);
}
E. LIS of Sequence
先正着求一发lis，再逆着求一发单调递减子序列
然后只要dp1[i]+dp2[i] - 1 == lis 就说明这个点肯定在其中一个里面
至于是不是独一无二的，就看dp1[i]是否是独一无二的就好啦
#include<iostream>
#include<stdio.h>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 100005
int b[maxn];
int a[maxn];
void add(int x,int val)
{
while(x<=)
{
b[x] = max(b[x],val);
x += x & (-x);
}
}
int get(int x)
{
int ans = ;
while(x)
{
ans = max(ans,b[x]);
x -= x & (-x);
}
return ans;
}
int dp1[maxn];
int dp2[maxn];
int ans[maxn];
map<int,int> H;
int main()
{
int n;scanf("%d",&n);
int LIS = ;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
dp1[i] = + get(a[i]-);
add(a[i],dp1[i]);
LIS = max(LIS,dp1[i]);
}
reverse(a+,a++n);
memset(b,,sizeof(b));
for(int i=;i<=n;i++)
{
a[i] = - a[i] + ;
dp2[i] = + get(a[i] - );
add(a[i],dp2[i]);
}
reverse(dp2+,dp2++n);
for(int i=;i<=n;i++)
{
if(dp1[i]+dp2[i]-!=LIS)ans[i]=;
else H[dp1[i]]++;
}
for(int i=;i<=n;i++)
{
if(ans[i]!=&&H[dp1[i]]==)
{
ans[i]=;
}
}
for(int i=;i<=n;i++)
if(ans[i]==)
cout<<"";
else if(ans[i]==)
cout<<"";
else if(ans[i]==)
cout<<"";
}
/*
10
2 2 2 17 8 9 10 17 10 5
*/