D. Almost Difference

http://codeforces.com/contest/903/problem/D

• long double 确实顶

#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<ll,ll> num;
long double sum[200005],ans=0;;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        long double nn;cin>>nn;   	
        if(i==0) 
        {
            sum[i]=nn;	
        }
        else 
        {
            sum[i]=sum[i-1]+nn;
            ans=ans+i*nn-sum[i-1]+num[nn+1]-num[nn-1];		
        }
        num[nn]+=1;
    }
    cout << fixed << setprecision(0) << ans << endl;
    return 0;
}

E. Swapping Characters

http://codeforces.com/contest/903/problem/E

• 汉明距离这个点信息论学过，但是确实没想到
• 训练时没想到暴力，在巧妙做法的猜测中渐行渐远
• 预处理第一个串串和其他串的汉明距离，枚举交换时减去交换前两个字母的贡献再加上交换后的贡献来更新汉明距离，若与其他串汉明距离都为2或0即为答案（0的情况需要先判断串中是否含有重复字母），复杂度O(k*k*n）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005,maxk = 2505;
string s[maxn];
int hanm[maxn];
int main()
{
    int n,k;
    cin>>n>>k;
    cin>>s[0];
    bool flag = 0;
    for(int i=0;i<k;i++)
    {
        for(char j = 'a';j<='z';j++)
        if(count(s[0].begin(),s[0].end(),j)>1) flag = 1;
    }
    for(int i=1;i<n;i++)
    {
        cin>>s[i];
        for(int j=0;j<k;j++)
        {
            hanm[i]+=(s[i][j]!=s[0][j]);
        }
        string a = s[0],b = s[i];
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        if(a!=b)
        {
            cout<<-1<<endl;
            return 0;
        }
    }
    for(int i=0;i<k;i++)
        for(int j=i+1;j<k;j++)
        {
            bool f = 1;
            for(int l=1;l<n;l++)
            {
                int cnt=hanm[l];
                cnt-=(s[0][i]!=s[l][i]);
                cnt-=(s[0][j]!=s[l][j]);
                cnt+=(s[0][i]!=s[l][j]);
                cnt+=(s[0][j]!=s[l][i]);
                if((cnt==0&&flag)||cnt==2) continue;
                else {
                    f = 0;
                    break;
                }	
            }
            if(f)
            {
                swap(s[0][i],s[0][j]);
                cout<<s[0]<<endl;
                return 0;
            }
                
        }
    cout<<-1<<endl;
    return 0;
}